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

74

THEORY OF NUMBERS

where v is to be the smallest exponent for which the congruence
is true. Since g is a primitive X-root of (i) v is a multiple of
X(pial... pr'). Since g is a primitive X-root of (2) v is a
multiple of X (pa+). Hence it is a multiple of X(m). But
gX(m) i mod m; therefore v=X(m). That is, g is a primitive
X-root modulo m.
The theorem as stated now follows at once by induction.
There is nothing in the preceding argument to indicate
that the primitive X-roots modulo mn are all in a single set
obtained by taking powers of some root g; in fact it is not in
general true when m contains more than one prime factor.
By taking powers of a primitive X-root g modulo mi one
obtains {NX(m)} different primitive X-roots modulo m. It is
evident that if 7 is any one of these primitive X-roots, then the
same set is obtained again by taking the powers of y. We may
say then that the set thus obtained is the set belonging to g.
II. If X(m)>2 the product of the 0{X(m) } primitive x-roots
in the set belonging to any primitive X-root g is congruent to i
modulo m.
These primitive X-roots are
v,~l1 g~21
g 71 gC2,.* gC2
where
I, C1) C2,... C.
are the integers less than X(m) and prime to X(w). If any one
of these is c another is X(in)-c, since X(m) > 2. Hence
I+Ci+C2+... +c=-o modX(m).
Therefore
gl ++ci +C2 + +C I + m ood im.
From this the theorem follows.
COROLLARY. The product of all the primitive X-roots modulo
m is congruent to i modulo m when X(m)> 2.