60 HISTORY OF THE THEORY OF NUMBERS. [CHAP, m

proved in 1681 (p. 50). Mahnke gave reasons (pp. 54-7) for believing that Leibniz rediscovered independently Fermat's theorem before he became acquainted, about 1681-2, with Fermat's Varia opera math, of 1679. In 1682 (p. 42), Leibniz stated that (p— 2)1=1 (mod p) if p is a prime [equivalent to Wilson's theorem], but that (p— 2)l=m (mod p), if p is composite, m having a factor > 1 in common with p.

De la Hire8 stated that if fc2r+1 is divided by 2(2r+l) we get A; as a remainder, perhaps after adding a multiple of the divisor. For example, if Jf is divided by 10 we get the remainder k. He remarked that Can4 had observed that the cube of any number fc<6 has the remainder k when

divided by 6.

L. Euler9 stated Fermat's theorem in the form: If n+l is a prime dividing neither a nor b, then a71— bn is divisible by n+l. He was not able to give a proof at that time. He stated the generalization: If e=pm~1(p — 1) and if p is a prime, the remainder obtained on dividing ae by pm is 0 or 1 [a special case of Euler14]. He stated also that if m, n, p, . . . are distinct primes not dividing a and if A is the L c. m. of m — 1, n — 1, p — 1, . . ., then aA— 1 is divisible by mnp. . . [and ak — 1 by mr n* . . .if k = A mr~ln8~l . . .].

Euler10 first published a proof of Fermat's theorem. For a prime p,

Hence if ap— a is divisible by p, also (l+a)p— (1+d) is, and hence also (a-f2)p-(a+2),. . ., (a-l-b)p-(a-f 6). Fora=2, 2P- 2 was proved divisible by p. Hence, writing x for 2-j-b, we conclude that zp— x is divisible by p for any integer x.

G. W. Kraft11 proved similarly that 2p-2=wp.

L. Euler' s12 second proof is based, like his first, on the binomial theorem. If a, fe are integers and p is a prime, (a+b)p— ap-fcp is divisible by p. Then, if ap— a and 6P— & are divisible by p, also (a+6)p — a — b is divisible by p. Take 6=1. Thus (a-fl)p— a — 1 is divisible by p if ap — a is. Taking a =1,2, 3,. . . in turn, we conclude that 2P— 2, 3P— 3, . . . , cp— c are divisible by p. -

L. Euler13 preferred his third proof to his earlier proofs since it avoids the use of the binomial theorem. If p is a prune and a is any integer not

*Hist. Acad. Sc. Paris, amide 1704, pp. 42-4; m£m., 358-362.

9Comm. Ac. Petrop., 6, 1732-3, 106; Comm. Arith., 1, 1849, p. 2. [Opera postuma, I, 1862,

167-8 (about 1778)].

10Comm. Ac. Petrop., 8, ad annum 1736, p. 141; Comm. Arith., 1, p. 21. uNovi Comm. Ac. Petrop., 3, ad annos 1750-1, 121-2. 12Novi Comm. Ac. Petrop., 1, 1747-8, 20; Comm. Arith., 1, 50. Also, letter to Goldbach,

Mar. 6, 1742, Corresp. Math. Phys. (ed. Fuss), I, 1843, 117. An extract of the letter is

given in Nouv. Ann. Math., 12, 1853, 47. 1JNovi Comm. Ac. Petrop., 7, 1758-9, p. 70 (ed. 1761, p. 49); 18, 1773, p. 85; Comm. Arith., 1,

260-9, 518-9. Reproduced by Gauss, Disq. Arith., art. 49; Werke, 1, 1863, p. 40.