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

PRIMITIVE ROOTS MODULO m

73

and show that it is true when m is the product of powers of
r+I different primes; from this will follow the theorem in
general.
Put m-plalp2a2... pr, +1 n=pla p2... r
and let h be a primitive X-root of
xX(n) I mod n. (I)
Then
h+nAy
is a form of the same root if y is an integer.
Likewise, if c is any primitive X-root of
+l) — I mod pr+l (2)
a form of this root is
r+1
where z is any integer.
Now, if y and z can be chosen so that
h+ny=c+pr+1 Z
the number in either member of this equation will be a common
primitive X-root of congruences (i) and (2); that is, a common primitive X-root of the two congruences may always be
obtained provided that the equation
al... pary-p+z=c-h
has always a solution in which y and z are integers. That this
equation has such a solution follows readily from theorem
III of ~ 9; for, if c-h is replaced by i, the new equation has a
solution y, z; and therefore for y and z we may take y =y(c-),
z=(c -h).
Now let g be a common primitive X-root of congruences
(I) and (2) and write
gV i mod m,