CHAP, ill] FERMAT'S AND WILSON'S THEOREMS. 63
Finally, Lagrange proved the converse of Wilson's theorem: If n divides l + (n1)!, then n is a prime. For n=4m+l, n is a prime if (2-3.. .2m)2 has the remainder 1 when divided by n. For n=4w1, if (2m 1)! has the remainder =±= 1.
L. Euler20 also proved by induction from x=n to n+1 that
\ / vyi* xy
which reduces to (1) for x=p1, a=p; and more generally,
D'Alembert21 stated that the theorem that the difference of order m of am is ml had been long known and gave a proof.
L. Euler22 made use of a primitive root a of the prune p to prove Wilson's theorem (though his proof of the existence of a was defective). When 1, a, a2, . . . , ap~2 are divided by p, the remainders are 1, 2, 3, . . . , p 1 in some order. Hence a(p~1J (p"2)/2 has the same remainder as (p 1) !. Taking p > 2, we may set p=2n+l. Since an has the remainder 1, then ana2n(n^\ and hence also (p 1)1, has the remainder 1.
P. S. Laplace23 proved Fermat's theorem essentially by the first method of Euler10 without citing him: If a is an integer <p not divisible by the prime p,
Hence by induction a*"1 1 is divisible by p. For a>p, set a=np+q and use the theorem for q.
He gave a proof of Euler's14 generalization by the method of powering : if n=ptlp1111. . ., where p, pi, . . . are distinct primes, and if a is prime to n, then a* 1 is divisible by n, where
Set aQ = s. Then av l = xr l is divisible by x l. Using the binomial theorem and a""1 l = hp, we find that x l is divisible by pM.
"Novi Comm. Ac. Petrop., 13, 1768, 28-30.
31Letter to Turgot, Nov. 11, 1772, in unedited papers in the Biblioth&que de 1'Institut de France. Cf. Bull. Bibl. Storia Sc. Mat. e Fis., 18, 1885, 531.
"Opuscula analytica, St. Petersburg, 1, 1783 [Nov. 15, 1773], p. 329; Comm. Arith., 2, p. 44; letter to Lagrange (Oeuvres, 14, p. 235), Sept. 24, 1773; Euler's Opera postuma, I, 583.
2JDe la Place, Throne abnSge'e des nombres premiers, 1776, 16-23. His proofs of Fennat's and Wilson's theorems were inserted at the end of Bossut's AlgSbre, ed. 1776, and reproduced by S. F. Lacroix, Trait6 du Calcul Diff. Int., Paris, ed. 2, vol. 3, 1818, 722-4, on p. 10 of which is a proof of (2) for a=x by the calculus of differences.