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

72

THEORY OF NUMBERS

From the theory of primitive 0-roots already developed
it follows that primitive X-roots always exist when m is a power
of any odd prime, and also when m= i, 2, 4; for, for such values
of m we have X(m) = +(m).
We shall next show that primitive X-roots exist when m= 2=,
a> 2, by showing that 5 is such a root. It is necessary and sufficient to prove that 5 belongs modulo 2' to the exponent
2a-2= )(2a). Let d be the exponent to which 5 belongs modulo
2a. Then from theorem II of ~ 32 it follows that d is a divisor
of 2a-2=X(2a). Hence if d is different from 2a-2 it is 2a3
or is a divisor of 2 -3. Hence if we can show that 523 is not
congruent to i modulo 2. we will have proved that 5 belongs
to the exponent 2a-2. But, clearly,
2a — 3 (I + 22)2 — + I + 2a-1 2a
where I is an integer. Hence
52a -3I mod 2.
Hence 5 belongs modulo 2" to the exponent X(2").
By means of these special results we are now in position to
prove readily the following general theorem which includes
them as special cases:
I. For every congruence of the form
x(m) -I mod m
a solution g exists which is a primitive X-root, and for any such
solution g there are 0{X(m)} primitive roots congruent to powers
of g.
If any primitive X-root g exists, gv is or is not a primitive
X-root according as v is or is not prime to X(m); and therefore
the number of primitive X-roots which are congruent to powers
of any such root g is 0 X(m) }.
The existence of a primitive X-root in every case may easily
be shown by induction. In case m is a power of a prime the
theorem has already been established. We will suppose that
it is true when m is the product of powers of r different primes