92 HISTORY OF THE THEOEY OF NUMBERS. [CHAP, in
divisible by n. From this fact Leibniz concluded erroneously that the expression .itself is not divisible by n.
Chr. GoKkach210 stated that (a+b)p~ap—bp is divisible by p also when p is any composite number. Euler (p. 124) points out the error by noting that 235—2 is divisible by neither 5 nor 7.
In 1769 J. H. Lambert15 (p. 112) proved that, if dm~l is divisible by a, and dn — 1 by 6, where a, b are relatively prune, then dc — 1 is divisible by ab if c is the 1. c. m. of m, n (since divisible by dm — 1 and hence by a). This was used to prove that if g is odd [and prune to 5] and if the decimal fraction for 1/g has a period of g—1 terms, then g is a prime. For, if g = ab [where a, 6 are relatively prime integers > 1], I/a has a period of m terms, m^ a — 1, and 1/6 a period of n terms, n^b—1, so that the number of terms in the period for 1/g is 5^(a~l)(& —1)/2<<7—1. Thus Lambert knew at least the case k = 10 of the converse of Fermat's theorem (Lucas214'217).
An anonymous writer 211 stated that 2n-}-l is or is not a prune according as one of the numbers 2rl=fc= 1 is or is not divisible by n. F. Sarrus212 noted the falsity of this assertion since 2170—1 is divisible by the composite number 341. *
In 1830 an anonymous writer43 noted that a71"1 — 1 may be divisible by n when n is composite. In a?~l = kp+1, where p is a prime, set k = \q. Then a(p-i)«si (mod pq). Thus a^"1^! if a^1^! (mod pq), and the last will
holdif q—1 is a multiple of p —1; for example, if p = 11, q = 31, a = 2, whence 2340=! (m0(j 341)
V. Bouniakowsky213 proved that if N is a product of two primes and if N—1 is divisible by the least positive integer a for which 2a=l, whence 2^~a=l (mod N), then each of the two primes decreased by unity is divisible by a. He noted that 36=1 (mod 91 ==7-13).
E. Lucas214 noted that 2n"1=l (mod n) torn = 37-73 and stated the true converse to Fermat's theorem: If a* —1 is divisible by p for x = p — 1, but not for x<p — l, then p is a prime.
F. Proth215 stated that, when a is prime to n, n is a prime if a*= 1 (mod n) for x = (n—1)/2, but for no other divisor of (n —1)/2; also, if ax= 1 (mod n) for x-n—1, but for no divisor <-\/n of n — 1. If w = w2*+l, where m is odd and < 2k, and if a is a quadratic non-residue of n, then n is a prime if and only if a(n~1)/2^= -1 (mod n). If p is a prune > \-\/n, n = mp +1 is a prime if a71""1 — ! is divisible by n, but am±l is not.
*F. Thaarup218 showed how to use a71""1^! (mod n) to tell if n is prime. E. Lucas217 proved the converse of Fermat's theorem: If ax=l (mod n) for x = n—1, but not for x a proper divisor of n — 1, then n is a prime.
310Corresp. Math. Phys. (ed. Fuss), I, 1843,122, letter to Euler, Apr. 12, 1742.
211Armales de Math. (ed. Gergonne), 9, 1818-9, 320.
21276id., 10, 1819-20, 184-7.
213Me*m. Ac. Sc. St. Pftersbourg (math.), (6), 2,1841 (1839), 447-69; extract in Bulletin, 6, 97-8.
214Assoc. fraiwj. avanc. sc., 5,1876, 61; 6, 1877, 161-2; Amer. Jour. Math., 1, 1878, 302.
216Comptes Rendus Paris, 87, 1878, 926.
218Nyt Tidsakr. for Mat., 2A, 1891, 49-52.
217Th6orie des nombres, 1891, 423, 441.