The theory of numbers, by Robert D. Carmichael ...

PRIMITIVE ROOTS MODULO m

b9

Therefore it is evident that x can be so chosen that -y 1-I
is not divisible by p2. Hence there exists a primitive root y
modulo p such that -~-l-I is not divisible by p2. Q. E. D.
We shall now prove that this integer y is a primitive root
modulo pa, where a is any positive integer.
If
7^ mod p,
then k is a multiple of p-I, since 7 is a primitive root modulo
p. Hence, if
-Y=I mod pa,
then k is a multiple of p-I.
Now, write
y-l=I+hp.
Since yp- -I is not divisible by p2, it follows that h is prime
to p. If we raise each member of this equation to the power
fpa-2, A-2, we have
yp P-2(p-1) I +pa-lh+paI,
where I is an integer. Then if
yp — 2 (p — 1I mod p,
mP ust be divisible by p. Therefore the exponent of the lowest
power of y which is congruent to i modulo pa is divisible by
pa-l. But we have seen that this exponent is also divisible
by p-I. Hence the exponent of 7 modulo pa is p~-l(p-I)
since (p^) =p-l(p -I). That is, - is a primitive root modulo pa.
It is easy to see that no two numbers of the set, 2, 73,,pa- (p-1) (A)
are congruent modulo pa; for, if so, y would belong modulo pa
to an exponent less than pa~-(p- ) and would therefore not
be a primitive root modulo pa. Now every number in the set