70 HISTORY OF THE THEORY OF NUMBERS. [CHAP.III A. L. Crelle58 proved the generalized Wilson theorem. By pairing each root a of #2=1 (mod s) with the root s—cr, and each integer a<s, prime to s and not a root, with its associated number a', where aa'==l (mod s), we see that the product of all the integers < s and prime to s is = + 1 or — 1 (mod s) according as the number n of pairs of roots cr, s— cr is even or odd. To find n, express s in every way as a product of two factors u, v, whose g. c. d. is 1 or 2; in the respective cases, each factor pair gives a single root cr or two roots. Treating four subcases at length it is shown that the number of factor pairs is 2k in each case, where k is the number of distinct odd primes dividing s; and then that n is odd if s = 4, pm or 2pn, but even if n is not of one of these three forms. A. Cauchy58" proved Fermat's theorem as had Leibniz.4 V59 (S. Earnshaw?) proved Wilson's theorem by Lagrange's method and noted that, if ST is the sum of the products of the roots of AQxm-{-AiXm~1-\- . . . ==0 (mod p) taken r at a time, then A<yS»»— (— 1)*A< is divisible by p. Paolo Gorini60 proved Euler's theorem 6's=l (mod A), where £=<£(A), by arranging in order of magnitude the integers (A) p', p", . . . , p(f} which are less than A and prime to A. After omitting the numbers in (A) which are divisible by 6, we obtain a set (B) g', . . ., q(l\ Let g(co) be the least of the latter which when increased by A gives a multiple of 6 : (C) g(w)+A=p(a)&. The numbers* (A) coincide with those in sets (B) and (D) : (D) p'^p'V..,^*-1^ Hence by multiplication and cancellation of p', . • •> p(a~l\ (F) g'-.-g^V-^pW..^. To each number (B) add the least multiple of A which gives a sum divisible by 6, say (G) g'+0'A,..., g(Z)+0(9A. The least of these is 4(w)-|-A= p(a)6, by (C). Each number (G) is <6A and all are distinct. The quotients obtained by dividing the numbers (G) by 6 are prime to A and hence included among the p(a), ..., p(i\ whose number is t—a+l = l, so that each arises as a quotient. Hence (H) n(gw+0(i)A) = PA+g'- . Yz)=p(aVa+1) • • .p(0&'-a+1. Combine this with (F) to eliminate the p's. We get qf. . .ga^y-'+^PA+g'. . .q(l\ qf . . .g® (&'-!)= PA, 58Jour. fur Math., 20, 1840, 29-56. Abstract in Bericht Akad. Wiss. Berlin, 1839, 133-5. 68*M6m. Ac. Sc. Paris, 17, 1840, 436; Oeuvres, (1), 3, 163-4. "Cambr. Math. Jour., 2, 1841, 79-81. 60Annali di Fisica, Chimica e Mat. (ed., G. A. Majocchi), Milano, 1, 1841, 255-7. *To follow the author's steps, take A = 15, 6 = 2, whence t =8, Z = 4, (A) 1, 2, 4, 7, 8, 11, 13, 14; (B) 1, 7, 11, 13; (C) 1+15 =8-2, p<«> =8, a = 5; (D) 2, 4, 8, 14; (F) l-7-ll-13-24 = 8-ll-13-14; (G) 1+15, 7+15, 11+15; 13+15, each g = 1; the quotients of the latter by 2 are 8, 11, 13, 14, viz., last four in (A); (H) P.15+1.7.11.13=8.11.13.14.24; the second member is 1-7-11-13-28 by (F). Hence 17-1M3 (28-l)=15P.