History Of The Theory Of Numbers - I

CHAP, ill] FEBMAT'S AND WILSON'S THEOREMS. 61
divisible by p, at most p — 1 of the positive residues < p, obtained by dividing 1, a, a2,... by p, are distinct. Let, therefore, a" and a", where M > t>, have the same residue. Then d""*—1 is divisible by p. Let X be the least positive integer for which ax—1 is divisible by p. Then 1, a, a2,.. ., ax~1 have distinct residues when divided by p, so that X^p —1. If X = p — 1, Fermat's theorem is proved. If X<p —1, there exists a positive integer k (k<p) which is not the residue of a power of a. Then k, ak, cfk,. .., ax~aA; have distinct residues, no one the residue of a power of a. Since the two sets give 2X distinct residues, we have 2X^p—1. If X<(p-1)/2, we start with a new residue s and see that s, as, a2s,.. ., ax""1s have distinct residues, no one the residue of a power of a or of cfk. Hence X^ (p —1)/3. Proceeding in this manner, we see that X divides p — 1. Thus a*"1 — 1 is divisible by ax—1 and hence by p.
L. Euler14 soon gave his fundamental generalization of Fermat's theorem from the case of a prime to any integer N:
Euler's theorem: If n=cf)(N) is the number of positive integers not exceeding N and relatively prime to N, then xn—1 is divisible by N for every integer x relatively prime to N.
Let v be the least positive integer for which xv has the residue 1 when divided by N. Then the residues of 1, x, x2,..., x'""1 are distinct and prime to N. Thus v^n. If v<n, there is an additional positive integer a less than N and prune to N. Then, when a, ax, ax2,.. ., ax""1 are divided by N, the residues are distinct from each other and from those of the powers of x. Thus, 2v^n. Similarly, if 2v<n, then 3v^n. It follows in this manner that v divides n.
J. H. Lambert15 gave a proof of Fermat's theorem differing slightly from the first proof by Euler.10 If b is not divisible by the prime p, fr7*"1 — 1 is divisible by p. For, set 6 = c+1. Then
.. .+1 .. .+l
where A is an integer. The intermediate terms equal
l_.rp-l_° J c+f c+1
Hence
+ 7
P
The theorem will thus follow by induction if / is shown to be integral. [Take p>2, so that p — 1 is even.] Then cp~l — 1 is divisible by c+1, and by the hypothesis for the induction, by p. Since cH-l = 6 is relatively prime to p, / is an integer.
14Novi Comm. Ac. Petrop., 8, 1760-1, p. 74; Comm. Arith., 1, 274-286; 2, 524-6. "Nova Acta Eruditorum, Lipsiae, 1769, 109.