Factorisation by Fermat's method: This method, dating from 1643, depends on a simple and standard algebraic identity. Fermat's observation is that if we wish to nd two factors of n, it is enough if we can express n as the di fference of two squares. This is because if n = a2 - b2, then we have immediately
n = a2 - b2 = (a+b)(a - b);
and so we have found two factors, a+b and a - b, of n.
It is possible here that a - b might equal 1, in which case we will only have found the trivial factorisation n = n x 1, but we can arrange matters so that this will only happen if n has no other factorisation - i.e., is prime.
At first glance, it may seem over-optimistic to hope that an expression for n as the di fference of two squares will exist.
But assume that n is odd, which we can always do if we are trying to factorise n. Then if n = uv and we put
a = 1/2(u+v) and b = 1/2(u - v);
we have n = a2 - b2 (note that a and b are both integers if n is odd), so that a representation of n as the difference of two squares does exist. (In fact, it is easy to see that the above formulae define a one-to-one correspondence between representations of n as the di erence of two squares and as the product of two factors - exercise.)