CHAPTER XIV.
METHODS OF FACTORING.
FACTOKING BY METHOD OF DIPFEKENCE OF Two SQUAKES.
Fermat1 described his method as follows: "An odd number not a square can be expressed as the difference of two squares hi as many ways as it is the product of two factors, and if the squares are relatively prime the factors are. But if the squares have a common divisor d, the given number is divisible by d and the factors by x/3* Given a number n, for example 2027651281, to find if it be prime or composite and the factors in the latter case. Extract the square root of n. I get r=45029, with the remainder 40440. Subtracting the latter from 2r+l, I get 49619, which is not a square in view of the ending 19. Hence I add 90061 = 2+2r+l to it. Since the sum 139680 is not a square, as seen by the final digits, I again add to it the same number increased by 2, i. e., 90063, and I continue until the sum becomes a square. This does not happen until we reach 1040400, the square of 1020. For by an inspection of the sums mentioned it is easy to see that the final one is the only square (by their endings except for 499944). To find the factors of n, I subtract the first number added, 90061, from the last, 90081. To half the difference add 2. There results 12. The sum of 12 and the root r is 45041. Adding and subtracting the root 1020 of the final sum 1040400, we get 46061 and 44021, which are the two numbers nearest to r whose product is n. They are the only factors since they are primes. Instead of 11 additions, the ordinary method of factoring would require the division by all the numbers from 7 to 44021."
Under Fermat,317 Ch. I, was cited Fermat's factorization of the number 100895508169 proposed to him by Mersenne in 1643.
C. F. Kausler2 would add I2, 22,... to N to make the sum a square.
C. F. Kausler3 proceeded as follows to express 4m+l in the form p2—g2. Then q is even, q = 2Q. Set p-g = 20+l. Then w = Q(204-l)+/3(/3+l). Subtract from m in turn the pronic numbers /3(/3+l), a table of which he gave on pp. 232-267, until we reach a difference divisible by 2/3+1.
Ed. Collins,4 in factoring N by expressing it as a difference of two squares, let g2 be the least odd or even square >N, according as N= 1 or 3 (mod 4), and set N = g2—r. If r is not a square, set r = /i2—c, where h2 is the even or odd square just >r, according as r is even or odd, whence c=4d,N — g2--/i2+4cL By trial find integers #, y such that both g2+x and h2+y are squares, while x — y = 4:d. Then N will be a difference of two squares.
fragment of a letter of about 1643, Bull. Bibl. Storia Sc. Mat., 12,1879, 715; Oeuvres de Fermat, 2,1894, 256. At the time of his letter to Mersenne, Dec. 26,1638, Oeuvres, 2, p. 177, he had no such method.
2Euler's Algebra, Frankfort, 1796, III, 2. Anbang, 269-283. Cf. Kausler, De Cribro Eratos-thenis, 1812.
»Nova Acta Acad. Petrop., 14, ad annos 1797-8 (1805), 268-289.
<Bull. Ac. Sc. St. Pe'tersbourg, 6, 1840, 84-88.