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

PRIMITIVE ROOTS MODULO in

67

Evidently every integer of the set belongs to some one and
only one of the exponents di, d2,..., dr. Hence we have
the relation
+(da~) + (d... + +(dr) = -. (I)
But,(dl)+ 2)+... +) (dr) =p-I. (2)
If then we can show that
4(da) ' (da) (3)
for i=i, 2,..., r, it will follow from a comparison of (i)
and (2) that
(di) = di).
Accordingly, we shall examine into the truth of (3).
Now the congruence
xdi= I mod p (4)
has not more than di roots. If no root of this congruence
belongs to the exponent di, then p(dd)=o and therefore in this
case we have {(dz) < (di). On the other hand if a is a root
of (4) belonging to the exponent di, then
a, a2, a3,.., ad (5)
are a set of di incongruent roots of (4); and hence they are the
complete set of roots of (4).
But it is easy to see that a' does or does not belong to the
exponent di according as k is or is not prime to di; for, if a'
belongs to the exponent t, then t is the least integer such that
kt is a multiple of di. Consequently the number of roots in
the set (5) belonging to the exponent dz is ~(d{). That is,
in this case {(do)= (di). Hence in general A(d) <0 (dJ).
Therefore from (i) and (2) we conclude that

{(di) = ~(di),

i= I, 2,..., Y