History Of The Theory Of Numbers - I

190 HlSTOEY OF THE THEORY OF NUMBERS. [CHAP. VII
V. A. Lebesgue41 noted that, given a primitive root g (g<p) of the prime p, we can find at once the primitive roots of pn. Let g' be the positive residue <p2 when gp is divided by p2 and set h=(g'—g)/p. Then
g+px+p2y (2/ = 0,. . ., pn-2-l; z = 0,. . ., p-1;
give pn~2(p-l) primitive roots. Replacing g by #*, where i is less than and prime to p — 1, we obtain <t> \(f>(pn) } primitive roots of pn. In particular, a primitive root of p2 is a primitive root of pn (Jacobi23). But, if /i = 0, g is not a primitive root of p2. Since
^fsp-a (mod pn), e^pn-l(p-l],
we can reduce by half the size of Jacobi's Canon.
D. A. da Silva42 gave two proofs that 3d =1 (mod p) has 4>(d) primitive roots, if d divides p — 1, and perfected the method of Poinsot9'30 for finding the primitive roots of a prime.
F. Landry420 was led to the same conclusion as Ivory.12 In particular, if p = 2*-f-l, or if p = 2n+l (n an odd prime) and a^p — 1, any quadratic non-residue a of p is a primitive root. For each prime p< 10000, at least one prime ^19 is a quadratic non-residue of p. Cauchy's14 congruence for the primitive roots is derived and proved.
G. Oltramare43 proved that — 3a22^ is a primitive root of the prime p = 2o0+l,if a^3,/3^3, 32a^l, 22^1 (modp); that, if
( — 1+qy— 3rx)53/2 is a primitive root of p; and analogous theorems. If a and 2a+l are primes, 2 or a is a primitive root of 2a+l, according as a is of the form 4n+l or 4n+3. If a is a prime 5^3 and if p = 2a-\-l is a prime and m>l, then 3 is a primitive root of p unless S^^ + lsO (mod p). [Cf. Smith.47]
P. Buttel44 attributed to Scheffler (Die unbestimmte Analytik, 1854, §142) the method of Crelle18 for finding the residues of powers.
C. G. Reuschle's45 table C gives the Haupt-exponent (i. e., exponent to which the number belongs) (a) of 10, 2, 3, 5, 6, 7 with respect to all primes p< 1000, and the least primitive root of p; (V) of 10 and 2 for 1000<p<5000 and a convenient primitive root; (c) of 10 for 5000<p< 15000 (no primitive root given). Numerous errata have been listed by Cunningham.110
Allegret46 stated that if n is odd, n is not a primitive root of a prime 22Xn+l, X>0; proof can be made as in Lebesgue.38
"Comptes Rendus Paris, 39, 1854, 1069-71; same in Jour, de Math., 19, 1854, 334-6. 42Proprietades geraes et resoluQao directa das Congruencias binomias, Lisbon, 1854. Report
by C. Alasia, Rivista di Fisica, Mat. e Sc. Nat., Pavia, 4, 1903, 25, 27-28; and Annaes
Scientificos Acad. Polyt. do Porto, Coimbra, 4, 1909, 166-192. 4WTroisi6me ine'moire sur la the"orie des nombres, Paris, 1854, 24 pp. «Jour. fur Math., 49, 1855, 161-86. "Archiv Math. Phys., 26, 1856, 247. *5Math. Abhandlung. . .Tabellen, Prog. Stuttgart, 1856; full title in the chapter on perfect
numbers.108 «Nouv. Ann. Math., 16, 1857, 309-310.