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

PRIMITIVE ROOTS MODULO m

65

It is now evident that the process may be continued until
all the numbers of the set (B) have been separated into classes,
each class containing d integers, thus:
(I) ao, al, a02,..., d-1,
(II) ho, 21, 02,..., d- 1,
(III) 7o, 71, 72,.,,d-,
( ) X0, Xl, 2, *. *, Xd-1.
The set (B), which consists of f(m) integers, has thus been
separated into classes, each class containing d integers. Hence
we conclude that d is a divisor of ~(m). Thus we have a second
proof of the theorem:
II. If a and m are any two relatively prime integers and d
is the exponent to which a belongs modulo n, then d is a divisor
of 0(m).
In our classification of the numbers (B) into the rectangular
array above we have proved much more than theorem II;
in fact, theorem II is to be regarded as one only of the consequences of the more general result contained in the array.
If we raise each member of the congruence
ad i mod n
to the (integral) power ~(m)/d, the preceding theorem leads
immediately to an independent proof of Fermat's general
theorem.
~ 34. DEFINITION OF PRIMITIVE ROOTS
DEFINITION. Let a and m be two relatively prime integers.
If the exponent to which a belongs modulo m is ~(m), a is said
to be a primitive root modulo m (or a primitive root of m).
In a previous chapter we saw that the congruence
ax(m) = mod m