Recently, I came across a simple yet elegant method of finding factors of a given (huge) number, due to the great mathematician Fermat. The greatness of this method is that it is a better attempt than finding out all factors of n less than sqrt n.

The method goes as follows:
Given an odd integer n in NN, we can safely assume that it is odd, (because if it were even, then 2 would be an obvious factor). Now to find (odd) numbers \a and \b such that n=a.b

Since both \a and b are odd, n=a.b = ((a+b)/2+(a-b)/2)((a+b)/2-(a-b)/2)=((a+b)/2)^2-((a-b)/2)^2 so invariably, one must begin his search of factors of n as the difference of two squares, i.e. find x and y such that n=x^2-y^2 or rather, find an x such that x^2-n=y^2. Now look at the numbers x^2-n, (x+1)^2-n, (x+2)^2-n, (x+3)^2-n… and find a number m such that m^2-n is a square. This process must terminate because
eventualy we arrive at ((n+1)/2)^2-n=((n-1)/2)^2 giving the trivial factorization n=n.1 If this stage is reached without a square difference discovered earlier, then n is prime.

In a letter to Fermat, Mersenne had requested the possible factorization of the number 100895598169. Using this method, Fermat replied almost immediately, that the number is the product of 898423 and 112303, both of which are primes.

Let us see a more down-to-earth example:
Assume n=851. The least integer greater than 851 is 30. Now, 30^2-851=49=7^2. So, 851=30^2-7^2=37.23


post signature