Explain Factorisation by Fermats method

Question

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 difference of two squares. This is because if n = a² - b², then we have immediately

n = a² - b² = (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 difference 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 = a² - b² (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 dierence of two squares and as the product of two factors - exercise.)