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:
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=a^{2}−b^{2} [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:
[1.6]
And
[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
[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=a^{2}−b^{2} [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=2^{2}−1^{2}, 5=3^{2}−2^{2}
For even integers we have: 4·1=4·(1^{2}−0^{2}), 2·3=2·(2^{2}−1^{2}), 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)=3^{2}−0^{2}, and (5-4)(5+4)=5^{2}−4^{2}
So for odd numbers we seek a and b such that:
n=a^{2}−b^{2}
We can start with a_{1}, where a_{1}
is the smallest integer greater than √(n), or ceil
(√(n)). For instance, for 91, we start with a_{1}
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 a_{k}^{2}−n
or:
Δa_{k}=a_{k}^{2}−n
If Δak_{} is a perfect square, then
b=√(Δa_{k}).
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 10^{2}-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. 8^{2}-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 a_{1}=8,
Δa_{1}=8^{2}-51=13.This isn't a perfect square. So try the next number up, 9. a_{2}=9,
Δa_{2}=9^{2}-51=30. Still no perfect square, so try 10. a_{3}=10,
Δa_{3}=10^{2}-51=49. At last a perfect square: 7^{2}. So a_{3}-b=(10-7) and a_{3}+b=(10+7), giving us 3 and 17 as factors of 51. If we continue seeking more factors: a_{4}=11,
Δa_{4}=11^{2}-51=70. a_{4}+√(Δa_{4}) ≥ n, 11+√(70_{}) ≥ 51 a_{5}=12,
Δa_{5}=12^{2}-51=93. a_{6}=13,
Δa_{6}=13^{2}-51=118. ... a_{32}=26,
Δa_{32}=26^{2}-51=625. A perfect square: 25^{2}. If we reach the end point, then we can stop, knowing we cannot find any more factors.
So a_{32}-b_{32}=(26-25) and a_{3}+b=(26+25), giving us 1 and 51 as factors of 51.Using the formula below, a_{32}+√(Δa_{32}) ≥ 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 2356987413860^{2}-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
Δa_{k}=a_{k}^{2}−
n=b_{k}^{2}.
Therefore:
a_{k}+√(Δa_{k})
≤ n
Because:
b_{k}=√(Δa_{k})
So when a_{k}+√(Δa_{k}) ≥
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
a_{1}=8
a^{2}
−n
b^{2}
8^{2}
−63
1=1^{2}
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
a_{1}=475
a^{2}
−n
b^{2}
475^{2}
−225621=
4 (2^{2})
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 a_{1}=7
The following was computed mainly using a spreadsheet:
Number,
n=45
Factors
Comments
k
a_{k}
a_{k}^{2}-n (Δa_{k})
Difference, (a_{k}^{2}-n)−(a_{k-1}^{2}-n)
b=√(a_{k}²-n)
Perfect
Square?
x
y
1
7
4
2
yes
5
9
2
8
19
15
4.36
no
no
no
3
9
36
17
6
yes
3
15
4
10
55
19
7.42
no
no
no
5
11
76
21
8.72
no
no
no
6
12
99
23
9.95
no
no
no
7
13
124
25
11.14
no
no
no
8
14
151
27
12.29
no
no
no
9
15
180
29
13.42
no
no
no
10
16
211
31
14.53
no
no
no
11
17
244
33
15.62
no
no
no
12
18
279
35
16.7
no
no
no
13
19
316
37
17.78
no
no
no
14
20
355
39
18.84
no
no
no
15
21
396
41
19.9
no
no
no
16
22
439
43
20.95
no
no
no
17
23
484
45
22
yes
1
45
We can stop when a_{k}+√(Δa_{k}) ≥
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 a^{2}-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: a_{k+1}=Δa_{k}+2•a_{k}+1 That is, we get the next "b_{2}" 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
a^{2}
−n
b^{2}
9930=98604900^{2}
−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'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: