# Fermat's method of factoring

**Fermat's method of factoring** consists of finding
*x* and *y* such that
*x*^{2}-*y*^{2}=*n*.
The right side of the equation factors
into (*x*-*y*)(*x*+*y*), and
if *x*-*y* is not one, then you have
found a non-trivial factorization.

There exists several easy extensions
to this idea. For example, instead of solving
*x*^{2}-*y*^{2}=*n*,
we try to find *x* and *y* such that
*x*^{2} ≡ *y*^{2}
(mod *n*). This means *n* divides
*x*^{2}-*y*^{2},
so if *x* is not congruent to
__+__*y* modulo *n*, then
gcd(*x*-*y*,*n*) or
gcd(*x*+*y*,*n*)
must be a
non-trivial factor of *n*.

For example, suppose we wish to factor
*n*=91. The first few squares (modulo
91) are as follows:

1, 4, 9, 16, 25, 36, 49, 64, 81, 9, 30, 53, 78, ...

So we see 3^{2} ≡ 10^{2} (mod 91),
and expect either gcd(10-3,91)=7 or gcd(10+3,91)=13
to be a proper divisor of 91. Both are!

Fermat's method (and the simple extensions to it above) are not very efficient in finding factors themselves, but are theoretically important in that many more modern methods such as: the quadratic sieve, multiple polynomial quadratic sieve, and the special and the general number field sieves are all based upon this method.

Contributed by Lucas Wiman

**References:**

- Burton97 (section 5.2)
D. M. Burton,Elementary number theory, Third edition, McGraw-Hill, 1997. [Burton's texts are excellent introductions to elementary number theory and its history.]