View Single Post 2017-02-27, 14:39 #3 Dr Sardonicus   Feb 2017 Nowhere 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 by ALBERT H. BEILER 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.  