360 HISTORY OF THE THEORY OP NUMBERS. [CHAP;XIV
quadratic residues of p. Then r+afea* (mod p). Thus a*— r must be a quadratic residue. Reject from a*, . . . , an the terms for which at— r is not in the set. We get the possible residues of x modulo p. His method to factor an=*= 1 is the same as Dickson's118 and is applied to show that the factor (273+237+l)/(5-239-9929) °f 2146+1 is a prune in case it has no factor between 10500 and 108000.
Kraitchik22 extended the method of Lawrence.
F. J. Vaes23 applied his18 method to factor MersenneV number. The same was factored by various methods in L'Interme'diaire des Math&nat-iciens, 19, 1912, 32-5. J. Petersen, ibid., 5, 1898, 214, noted that its product by 8 equals k*+k, where fc= 898423.
METHOD or FACTORING BY SUM OP Two SQUARES. Frenicle de Bessy26 proposed to Fermat that he factor h given that ft=o2-f &* = <?+(?, as 221 = 100+121 = 196+25.
In 1647, Mersenne61 (of Ch. I) noted that a number is composite if it be a sum of two squares in two ways.
L. Euler26 noted that N is a prime if it is expressible as a sum of two squares in a single way, while if N = a2 + b2 = c2 -f cf, N is composite :
{(a~c
Euler27 proved, that, if a number 2V=4n+l is expressible as the sum of two relatively prime squares in a single way, it is a prime. For, if N were composite, then N= (a2-f Z>2)(c2+d2) is the sum of the squares of ac^=bd and ad=pbc, contrary to hypothesis. If N = a2+b2*=c?+d?, N is composite; for if we set a = c+x, d=b+y, and assume* that the common value of 2CX+X2 and 2by+y2 is of the form xyz, we get
whence x2+t/2 or (z2-f-y2)/4 is a factor of N. To express N as a sum of two squares in all possible ways, use is made of the final digit of N to limit the squares z2 to be subtracted in seeking differences N—x2 which are squares. Several numerical examples of factoring are treated in full.
Euler28 gave abbreviations of the work of applying the preceding test. For example, if 4n+l=5m+2=x2+2/2, then x and y are of the form
MSphinx-Oedipe, 1912, 61-4.
^L'enseignement math., 15, 1913, 333-4.
^euvres de Fermat. 2, 1894, 232, Aug. 2, 1641.
"Letters to Goldbach, Feb. 16, 1745, May 6, 1747; Corresp. Math. Phya. (ed., Fuss), I, 1843, 313, 416-9.
J7Novi Comm. Ac. Petrop., 4, 1752-3, p. 3; Comm. Arith., 1, 1849, 165-173.
*Euler gave a faultless proof in the margin of his posthumous paper, Tractatus, §570, Comm. Arith., 2, 573; Opera postuma, I, 1862, 73. We have (a+c)(o-c) = (6+d)(d-6) =pgrs, a+c=pg, a-c=rs, fe-fd «pr, d-b =*qs [since, if p be the g. c. d. of a-|-c, 6+d, then q(a—c) is divisible by r, whence a— c~rs]. Hence a2+b3~(p2+8s)(gs-f-r*)/4.
"Novi Comm. Ac. Petrop., 13, 1768, 67; Comm. Arith., 1, 379.