CHAP, vii] PRIMITIVE ROOTS, EXPONENTS, INDICES. 195
G. B. Mathews77 reproduced art. 81 of Gauss7 and gave a second proof by use of Cauchy's14 congruence X=0 for n—p — 1.
K. Zsigmondy78 treated the problem to find all integers K, relatively prime to given integers a and 6, such that cf^b* (mod K) holds for the given integral value 0-=7, but for no smaller value. For 6 = 1, it is a question of the moduli K with respect to which a belongs to the exponent 7. Set 7=n$t**, where the q's are distinct primes and #1 the greatest. Then all the primes K for which ^=6" (mod K) holds for tr=7, but for no smaller a, coincide with the prime factors of
tt(ay/Q-
in which the products extend over the combinations of qlt q2,... one, two,... at a time, provided that, if a^b" (mod gO for o-=7/g1Kl, but for no smaller <r, we do not include among the K's the prime qit which then occurs in A to the first power only. If the prime p is a K and if pe is the highest power of p dividing A, then pe is the highest power of p giving a K. The composite K's are now easily found. If a and b are not both numerically equal to unity, it is shown that there is at least one prime K except in the following cases: 7 = !, a-& = l; 7 = 2, a+&=±2/l (/x^l); 7 = 3, a = ±2, fc==Fl; 7 = 6, a = =*=2, & = =*=!. The case 6 = 1 shows that, apart from the corresponding exceptions, there exists a prime with respect to which the given integer a^^l belongs to the given exponent 7. As a corollary, every arithmetical progression of the type /rx+1 (^ = 1, 2,...) contains an infinitude of primes.
Zsigmondy79 considered the function AT(a) obtained from the above A by setting 6 = 1. If a is a primitive root of the prune p = l+y, the main theorem of the last paper shows that p divides AY(a). Conversely, 1+7 is a prime if it divides A. Thus, if all the primes of a set of integers possess the same primitive root a, any integer p of the set is a prime if and only if Ap-i(a) is divisible by p. Hence theorems due to Tchebychef34 imply criteria for primes. For example, a prime 22n-|-l has the primitive root 3 implies that 22n-fl is a prime if and only if it divides 3AH-1, where /c = 22\ Since =t=2 is a primitive root of any prime 2#+l such that q is a prime 4&± 1, we infer that, if q is a prime 4fc="= 1, then 2q+l is a prime if and only if it divides (2ff=*= 1)/(2=«=1). Since 2 is a primitive root of a prime 4.AT+1 such that N is an odd prime, we infer that, if N is an odd prime, 47V+1 is a prime if and only if it divides (22Ar+l)/5.
G. F. Bennett80 proved (pp. 196-7) the first theorem of Cauchy,26 and (pp. 199-201) the results of Sancery.61 If a and a' belong to exponents t and tf which contain no prime factor raised to the same power in each, then the exponent to which aa' belongs is the 1. c. m. of t and tf (p. 194).
"Theory of Numbers, 1892, 23-25. 78Monatshefte Math. Phys., 3, 1892, 265-284. "/6id., 4, 1893, 79-80. "Phil. Trans. R. Soc. London, 184 A, 1893, 189-245.