View Single Post
Old 2017-02-27, 14:39   #3
Dr Sardonicus
Dr Sardonicus's Avatar
Feb 2017

4,517 Posts

This reminds me of something I read lo, these many years ago in

Recreations in the Theory of Numbers The Queen of Mathematics Entertains


which (three cheers for the Information Age!) may be found here

In the chapter "Resolution" on factoring we find the following example:

Since any odd integer in excess of unity can be represented as the difference of two squares, we must ultimately arrive at a square if we add squares to an unknown odd number. But if the unknown should happen to be a prime, then it may take many steps before the sum is a square so that this method had best be abandoned if results are not obtained within a reasonable number of trials. Thus, even for so small a number as 9839, one would have to exhaust almost half of Barlow's table of squares before finding that 9839+49192 = 49202 or 9839 = (4920+4919)(4920-4919) = 9839ยท1, and that consequently 9839 is a prime.

OK, this is slightly cruder than Fermat's method (which is described just before), but only slightly. These simple methods become prohibitively laborious even for small numbers.
Dr Sardonicus is offline   Reply With Quote