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

68

THEORY OF NUMBERS

The result thus obtained may be stated in the form of the
following theorem:
I. If p is a prime number and d is any divisor of p-i, then
the number of integers belonging to the exponent d modulo p
is ~(d).
In particular:
II. There exist primitive roots modulo p and their number
is (p- I).
~ 36. PRIMITIVE ROOTS MODULO p", p AN ODD PRIME
In proving that there exist primitive roots modulo p", where
p is an odd prime and a> i, we shall need the following theorem:
I. There always exists a primitive root 7 modulo p for which
yP-1 -I is not divisible by p2.
Let g be any primitive root modulo p. If g1-'-I is not
divisible by p2 our theorem is verified. Then suppose that
gP-1-I is divisible by p2, so that we have
g-l I = kp2
where k is an integer. Then put
a=g+xp
where x is an integer. Then y-g mod p, and hence
h =gh mod p;
whence we conclude that r is a primitive root modulo p. But
-1_- I -i = gP-2 (p-I)(p-2) P-3x2p2+
2!
P(-I P-2X (P I)(p — 2)g-3X2p+
Hence
yP-1l-I-p(gP-2x) mod p2.