History Of The Theory Of Numbers - I

CHAP, vii] PKIMITIVE ROOTS, EXPONENTS, INDICES. 185
and q are primes, 2 and — 2 are primitive roots of p. If p=4g+l and g = 3n-f 1 are primes, 3 and —3 are primitive roots of p.
F. Minding16 gave without reference Gauss' second proof of the existence of primitive roots of a prime.
F. J. Richelot17 proved that, if p = 2m+l is a prime, every quadratic non-residue (in particular, 3) is a primitive root of p.
A. L. Crelle18 gave a table showing all prime numbers g 101 having a given primitive root; also a table of the residues of the powers of the natural numbers when divided by the primes 3,.. ., 101. His device19 for finding the residues modulo p of the powers of a will be clear from the example p = 7, a = 3. Write under the natural numbers <7 the residues of the successive multiples of 3 formed by successive additions of 3; we get
123456 362514.
Then the residues 3, 2, 6,... of 3, 32, 33,. .. modulo 7 are found as follows: after 3 comes the number 2 below 3 in the above table; after 2 comes the number 6 below 2 in the table; etc.
Crelle20 proved that, if p is a prime and X is prime to p —1 and <p — 1, the residues modulo p of zx range with z over the integers 1, 2,..., p — l. His proof that there exist <£(n) numbers belonging to the exponent n modulo p} if n divides p — l, is like that by Legendre.6
G. L. Dirichlet21 employed 0(fc) systems of indices for a modulus fc = 2yrp'T'..., where p, p',... are distinct primes, and X^3. Given any integer n prime to k, and primitive roots c, c',... of pw, p'*',.. ., we can determine indices a, /3, y, 7',... such that
ns (-!)•# (mod 2X), n^cy (mod pr), n = c'y (mod p"'),....
Michel Ostrogradsky22 gave for each prime p<200 all the primitive roots of p and companion tables of the indices and corresponding numbers. (See Jacobi23 and Tchebychef-M)
C. G. J. Jacobi23 gave for each prime and power of a prime < 1000 two companion tables showing the numbers with given indices and the index of each given number. In the introduction, he reproduced the table by Burckhardt, 1817, of the length of the period of the decimal fraction for 1/p, for each prime p^2543, and 22 higher primes. Of the 365 primes <2500, we therefore have 148 having 10 as a primitive root, and 73 of the form 4m+3 having —10 as a primitive root. Use is made also of the primes for which 10 or —10 is the square or cube of a primitive root.
"Anfangsgriinde der hoheren Arith., 1832, 36-37.
17Jour. fur Math., 9, 1832, p. 5.
18/6id., 27-53.
"Also, ibid., 28, 1844, 166.
JOAbh. Ak. Wiss. Berlin, 1832, Math., p. 57, p. 65.
"Ibid., 1837, Math., 45; Werke, 1, 1889, 333.
"Lectures on alg. and transc. analysis, I-II, St. P6tersbourg, 1837; Me*m. Ac. Sc. St. Pe"tera-
bourg, s<$r. 6, sc. math, et phys., 1, 1838, 359-85. "Canon Arithmeticus, Berlin, 1839, xl-f-248 pp. Errata, Cunningham.110'1"