182 HlSTOKY OF THE THEORY OF NUMBERS. [CHAP. VII
A. M. Legendre6 started with Lagrange's3 result that, if p is a prime and n is a divisor of p — 1, (1) zn = l (modp)
has n incongruent integral roots. Let n = z/V6 . . ., where i>, v',. .. are distinct primes. A root a of (1) belongs* to the exponent n if no one of an/", a7t/*', . . . is congruent to unity modulo p. For, if ae = l, 0<0<n, let a be the g. c. d. of 0, n, so that a — ny—Qz for integers y, 2; then
ate=:l, a'sa^'sa^sl, .
contrary to hypothesis. Next, of the n roots of (1), n/V satisfy xn/* = l (mod p), and n(l — 1/V) do not. Likewise, n(l — 1/V) do not satisfy £n/v'== 1; etc. It is said to follow that there are
numbers belonging to the exponent n modulo p. If
]3 belongs to the exponent va. If /3' belongs to the exponent /5, etc., the product /3/3' . . . is stated to belong to the exponent n.
C. F. Gauss7 gave two proofs of the existence of primitive roots of a prime p. If d is a divisor of p — 1, and ad is the lowest power of a congruent to unity modulo p, a is said to belong to the exponent d modulo p. Let \l/(d) of the integers 1, 2, . . . , p — 1 belong to the exponent d, a given divisor of p — 1 . Gauss showed that \l/ (d) = 0 or <j> (d) , 2 \f/ (d) = p — 1 = 2 4> (d) , whence \[,(d) =<t>(d). In his second proof, Gauss set p — 1 = aa6/9. . ., where a, 6, ... are distinct prunes, proved the existence of numbers A, B, . . . belonging to the respective exponents aa, Z>V . ., and showed that AB . . . belongs to the exponent p — 1 and hence is a primitive root of p.
Let a be a primitive root of p, b any integer not divisible by p, and e the integer, uniquely determined modulo p — l, for which ae = 6 (mod p). Gauss (arts. 57-59) called e the index of b for the modulus p relative to the base a, and wrote e = ind b. Thus
aind6^b (modp), ind 6b' = ind 6+ind b' (mod p-1).
Gauss (arts. 69-72) discussed the relations between indices for different bases and the choice of the most convenient base.
In articles 73-74, he gave a convenient tentative method for finding a primitive root of p. Form the period of 2 (the distinct least positive residues of the successive powers of 2); if 2 belongs to an exponent t<p — l, select a number b<p not in the period of 2, and form the period of b; etc.
If a belongs to the exponent t modulo p} the product of the terms in the period of a is =( — 1)/+1 (mod p), while the sum of the terms is =0 unless asl (arts. 75,79).
6M<5m. Ac. R. Sc., Paris, 1785, 471-3. Theorie-des nombres, 1798, 413-4; ed. 3, 1830,
Nos. 341-2; German transl. by Maser, 2, pp. 17-18. *This term was introduced later by Gauss.7 7Disquisitiones Arith., 1801, arts. 52-55.