nav.gif (1245 bytes)mathematics

Ken Ward's Mathematics Pages

Number Theory: Fermat's Factorisation Method

Fermat's factorisation method uses that fact that any number can be expressed as the difference between two squares. It always works, and works very quickly when the factors are near the root of the number. When the factors aren't near the root of the number, the method works very slowly, perhaps as slowly as trial division, with far more work!
See also:


Number Theory Contents

Page Contents

  1. Rationale
    1. Every Integer can be written as the Difference between Two Squares
    2. Fermat's Prime Factorisation Method
    3. When to Stop
  2. Examples

Rationale

Every Integer can be written as the Difference between Two Squares

What follows is a rationale and not a strict proof.
We wish to show that any integer, n, can be written as:
n=a2−b2  [1.1]

Because we are looking at factorisation, then n is odd. (If n is even, we know 2 is a factor, and can divide by 2.)

For any integer, n, we can write:
n=x•y [1.1a]
Where x and y are integers. If n is prime, then the two numbers will be equal to n and 1. Otherwise, they can also represent the other factors of n. The Fundamental Theorem of Arithmetic (According to Gauss) tells us that numbers can be written as the product of primes, so the factors x and y exist (Common sense tells us this).

x and y, in Equation 1.1a are odd integers, because n is odd.
Let
x=a+b [1.2]
And
y=a−b [1.3]

We can do this because 1.2 and 1.3 are indeterminate equations (Diaphantine Equations), which have a solution when gcd(1,1) divides x and gcd(1,-1) divides y, which it always does.

Therefore:, by respectively adding and subtraction 2.2 and 2.3, we get:
x+y=2a [1.4]
x-y=2b [1.5]

So:
divisibilityFermat.gif [1.6]
And
divisibilityFermat2.gif [1.7]

a and b are integers because x and y are both odd integers and the sum and difference of two odd integers is an even integer, which divides by 2.

Subtracting the squares of 1.6 and 1.7, we get
divisibilityFermat3.gif [2.6]
Of course we already know this, because 1.1a tells us:
n=x•y [1.1a, repeated]
Any odd number can, therefore, be represented as the difference between two squares.

Fermat's Prime Factorisation Method

We are mainly concerned with non-negative integers here; negative integers can be processed in the same way by supplying the necessary minus signs. Also we are concerned with odd integers, because we can always reduce an even integer to an odd one, and we are seeking a practical way to find factors.

We can express any odd integer, n, in the form:
n=a2−b2 [2.01]
or (factorised):
n=(a+b)(a−b) [2.02]
Where a and b are integers. If n is even, we know that 2 is a factor, and continue to divide by 2 until the number is odd.
For instance:
3=22−12, 5=32−22
For even integers we have: 4·1=4·(12−02), 2·3=2·(22−12), which is why we prefer to take out the 2 factors and deal with odd numbers.

When n is prime, then (a−b)=1 is the only solution (for non-negative integers). When n has factors, then there are more solutions than (a−b)=1.
For instance, if n=3, then
a-b=1, and a+b=3 are the only solutions. That is, a=2 and b=1, giving (2-1)(2+1)=3
And for 9, we have two solutions: (3-0)(3+0)=32−02, and (5-4)(5+4)=52−42

So for odd numbers we seek a and b such that:
n=a2−b2

We can start with a1, where a1 is the smallest integer greater than √(n), or ceil (√(n)). For instance, for 91, we start with a1 as the smallest integer greater than √91, which is 10.
Naturally, if n is a perfect square then we already have two non-trivial factors,the square roots. For instance, if n=81, and we find the square root, 9, we already have two roots.

In general, we compute ak2−n or:
Δak=ak2−n

If Δak is a perfect square, then b=√(Δak). And we can compute the factors (a−b) and (a+b). We can then examine the factors found to search for further factors, if required, perhaps by re-using Fermat's Method.

For 91, we compute  ceil(√(91))=ceil(9.5...)=10
102-91=9. As nine is a perfect square, we know (10-3)(10+3), or 7 and 13 are factors of 91.
Similarly, for 63, ceil(√(7.9...))=ceil(7.9...)=8.
82-63=1. As 1 is a perfect square, we know (8-1)(8+1), or 7 and 9 are factors of 63.

Fermat's method works quickly if the factors are near the root of the number, but otherwise, not so quickly, or even terribly slowly.

For instance, let n=51.
For 51, we compute  ceil(√(51))=8
a1=8, Δa1=82-51=13.This isn't a perfect square. So try the next number up, 9.
a2=9, Δa2=92-51=30. Still no perfect square, so try 10.
a3=10, Δa3=102-51=49. At last a perfect square: 72. So a3-b=(10-7) and a3+b=(10+7), giving us 3 and 17 as factors of 51.
If we continue seeking more factors:
a4=11, Δa4=112-51=70. a4+√(Δa4) ≥ n, 11+√(70) ≥ 51
a5=12, Δa5=122-51=93.
a6=13, Δa6=132-51=118.
...
 a32=26, Δa32=262-51=625. A perfect square: 252.
If we reach the end point, then we can stop, knowing we cannot find any more factors.
So a32-b32=(26-25) and a3+b=(26+25), giving us 1 and 51 as factors of 51.Using the formula below, a32+√(Δa32) ≥ 51, 26+√(625) ≥ 51, so we can stop as there are no more factors.
The morale here (From the large amount of work needed) is that we use Fermat's method for a few tries, but then use something else, perhaps even trial division. Fermat's method gives factors quickly when they are near the root of the number. Otherwise it is more work than trial division.

As a final example in this section, we factorise 5555389669094450920099599
For 5555389669094450920099599, we compute  ceil(√(5555389669094450920099599))=
ceil(2356987413859.9 ...)=2356987413860
23569874138602-5555389669094450920099599=1. As one is a perfect square, we know
(2356987413860 -1)(2356987413860 +1), or 2356987413859 and 2356987413861 are factors of 5555389669094450920099599. We obtain this result immediately.

The point is that Fermat's Method makes light work of difficult tasks under certain circumstances, but it can also make hard work of an easy problem.

When to Stop

If a=b, the number is a perfect square, which we would have discovered when finding the root. We can then further examine the roots to seek further factors, if required.

Because (a+b)(a −b)=n, and if n is not a perfect square, and a>b:
Then (a−b) cannot be less than 1. The greatest value of (a+b) is then n.
So:
(a+b)≤n
As
Δak=ak2− n=bk2.
Therefore:
ak+√(Δak) ≤ n
Because:
bk=√(Δak)
So when ak+√(Δak) ≥ n, we can stop, because there will be no more factors to be found

If the only factors found are n and 1, then n is prime.

Examples

Example 1

Factorise 63 (We are not ashamed to begin with a simple example!)
√(63)<8
a1=8
a2 −n b2
82 −63 1=12 This is a square number. (8+1)(8-1)=9•7=63, so the method gives factors immediately.

Example 2

Factorise 22,5621
√(225621)<475
a1=475
a2 −n b2
4752 −225621= 4 (22) We find a square number immediately, so b=2
a+b=475+2=477
a-b=475-2=473
So we have found the factors 473, 477. We can now further examine these factors to search for prime factors, if required.
(Neither 473 nor 477 is prime).
If there is a factor near the square root, Fermat's Method finds it quickly.


Example 3

This example shows a more complete example of Fermat's Method, and illustrates when to stop. The method finds factors, in this case, immediately. 
n=45
√(45)<7, so we start with a1=7

The following was computed mainly using a spreadsheet:

Number, n=45
FactorsComments
kak ak2-n (Δak) Difference,
(ak2-n)−(ak-12-n)
b=√(ak²-n) Perfect Square? x y
17 4 2 yes 5 9
28 19 154.36 no no no
39 36 176 yes 3 15
410 55 197.42 no no no
511 76 218.72 no no no
612 99 239.95 no no no
713 124 2511.14 no no no
814 151 2712.29 no no no
915 180 2913.42 no no no
1016 211 3114.53 no no no
1117 244 3315.62 no no no
1218 279 3516.7 no no no
1319 316 3717.78 no no no
1420 355 3918.84 no no no
1521 396 4119.9 no no no
1622 439 4320.95 no no no
1723 484 4522 yes 1 45We can stop when ak+√(Δak) ≥ n, here:
23+22=45, so we have found all the factors.

The above continues until we find our finishing point, which in the above case is when a=23, and b=22.

Looking at the 4th column, "Difference", which shows the difference between one a2-n value and the previous one (where possible), we can note it is a simple arithmetic series, with a difference of 2.

It is also possible to notice that in the example, that:
ak+1=Δak+2•ak+1
That is, we get the next "b2" value by adding to the current result double the current a value plus 1.

By this means, the arithmetic can be eased because we do not have to square numbers every time.

Example 4

The following example shows that even when the number is relatively large, Fermat's Method find the factors very quickly when they are close to the square root.n=98604899
√98604899<9930

a2 −n b2
9930=986049002 −98604899= 1 We immediately find a perfect square, so (9930+1)(9930-1)=9931•9929. We have established that the number isn't prime, and we can further examine the factors, if required. (They are, in fact, both prime!)







Ken Ward's Mathematics Pages


Faster Arithmetic - by Ken Ward

Ken's book is packed with examples and explanations that enable you to discover more than 150 techniques to speed up your arithmetic and increase your understanding of numbers. Paperback and Kindle:
Buy now at Amazon.com
Faster Arithmetic for Adults