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~apbp is divisible by p also when p is any composite number. Euler (p. 124) points out the error by noting that 2352 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 g1 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^b1, so that the number of terms in the period for 1/g is 5^(a~l)(& 1)/2<<71. 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 21701 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 q1 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 N1 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 = (n1)/2, but for no other divisor of (n 1)/2; also, if ax= 1 (mod n) for x-n1, 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 = n1, 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.