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

70

THEORY OF NUMBERS

(A) is prime to pa; their number is 0(py) = p -(p - ). Hence
the numbers of the set (A) are congruent in some order to the
numbers of the set (B):
al, a2, a3,..., apa-l(p-1), (B)
where the integers (B) are the positive integers less than pa
and prime to p".
But any number of the set (B) is a solution of the congruence
xpa-l(p-1) - i mod p. (I)
Further, every solution of this congruence is prime to pa. Hence
the integers (B) are a complete set of solutions of (i). Therefore
the integers (A) are a complete set of solutions of (i). But
it is easy to see that an integer 7k of the set (A) is or is not a
primitive root modulo p" according as k is or is not prime to
pa -l(p-I). Hence the number of primitive roots modulo
pa is { 1pa-l(p_)}The results thus obtained may be stated as follows:
II. If p is any odd prime number and a is any positive integer,
ihen there exist primitive roots nodulo p" and their number is
{ q(p"a)
~ 37. PRIMITIVE ROOTS MODULO 2pa, p AN ODD PRIME
In this section we shall prove the following theorem:
If p is any odd prime number and a is any positive integer,
then there exist primitive roots modulo 2pa and their number is
~{ 0(2pa)}.
Since 2pa is even it follows that every primitive root modulo
2pa is an odd number. Any odd primitive root modulo pa is
obviously a primitive root modulo 2p". Again, if 7 is an even
primitive root modulo pa then T+pa is a primitive root modulo
2pa. It is evident that these two classes contain (without
repetition) all the primitive roots modulo 2pa. Hence the
theorem follows as stated above.