196 HISTORY OF THE THEORY OF NUMBERS. [CHAP, vn
If 28+1 is the highest power of 2 dividing a2—!, where a is odd, the exponent to which a belongs modulo 2X is 2X~' if X>«, but, if X^s, is 1 if as 1, 2 if a2=l, a^l (mod 2X); the result of Lebesgue48 (p. 87) now follows (pp. 202-6). In case a is not prime to the modulus, there is an evident theorem on the earliest power of a congruent to a higher power (p. 209). If e is a given divisor of 0(w), there is determined the number of integers belonging to exponent e modulo m [cf. Erlerus25]. If a, a',. • • belong to the exponents t, t',... and if no two of the it'... numbers aVr'... (Q^r<t, 0^r'<*',...) are congruent modulo w, then a, a',... are called independent generators of the <t>(m) integers <m and prime to m (p. 195); a particular set of generators is given and the most general set is investigated (pp. 220-241) [a special problem on abelian groups].
J. Perott81 found a number belonging to an exponent which is the 1. c. m. of the exponents to which given numbers belong. If, for a prime modulus p, a belongs to an exponent t>l, and b to an exponent which divides t, then & is congruent to a power of a (proof by use of Newton's relations between the sums of like powers of a,..., a' and their elementary symmetric functions). Hence there exists a primitive root of p.
M. Frolov82 noted that all the quadratic non-residues of a prime modulus m are primitive roots of m if m = 22c-fl, m=2n+l or 4n+l with n an odd prime [Tchebychef34]. To find primitive roots of m "without any trial," separate the m—\ integers <m into sets of fours a, &, —a, — 8, where ab=l (mod m). Begin with one such set, say 1, 1, — 1, —1. Either a or m—a is even; divide the even one by 2 and multiply the corresponding =fc& by 2; we get another set of four. Repeat the process. If the resulting series of sets contains all m—1 integers <m, 2 and —2 are primitive roots if m=4/i+l, and one of them is a primitive root if ra=4/i — 1. If the sets just obtained do not include all m—1 integers <m, further theorems are proved.
G. Wertheim83 gave the least primitive root of each prime p < 3000.
L. Gegenbauer83a gave two expressions for the sum sk of those terms of a complete set of residues modulo p which belong to the exponent k, and evaluated 2sk/t f(t) with t ranging over the divisors of k.
G. Wertheim84 proved that any prune 24n+l has the primitive root 7. If p = 2n0+l is a prime and q is a prime >2, any quadratic non-residue m of p is a primitive root of p if w2n — 1 is not divisible by p. As corollaries, we get primes q of certain linear forms for which 2, 5, 7 are primitive roots of a prime 20+1 or 40+1; also, 3 is a primitive root of all primes 80+1 or 160+1 except 41; and cases when 5 or 7 is a primitive root of primes 8#+l, 160+1. There is given a table showing the least primitive root of each prime between 3000 and 3500.
81Bull. des Sc. Math., (2), 17,1, 1893, 66-83.
82Bull. Soc. Math, de France, 21, 1893, 113-128; 22, 1894, 241-5.
83Acta Mathematica, 17, 1893, 315-20; correction, 22, 1899, 200 (10 for p = 1021).
83>'Denkschr. Ak. Wiss. Wien (Math.), 60, 1893, 48-60.
"Zeitschrift Math. Naturw. Unterricht, 25, 1894, 81-97.