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

PRIMITIVE ROOTS MODULO IT

if a and m are relatively prime. Hence from the preceding
theorem we have at once the following:
II. The exponent d to which a belongs modulo m is a divisor
of both qf(m) and X(m).
~ 33. ANOTHER PROOF OF FERMAT'S GENERAL THEOREM
In this section we shall give an independent proof of the
theorem that the exponent d of a modulo m is a divisor of (p(m);
from this result we have obviously a new proof of Fermat's
theorem itself.
We retain the notation of the preceding section. We shall
first prove the following theorem:
I. The numbers
i, a, a2,.. a a-1 (A)
are incongruent each to each modulo m.
For, if aa-at modm, where o<a<d and o <d, a>3,
we have a~- -I mod m, so that d is not the exponent to which
a belongs modulo m, contrary to hypothesis.
Now any number of the set (A) is congruent to some number
of the set
al, a2,..., a (m). (B)
Let us undertake to separate the numbers (B) into classes
after the following manner: Let the first class consist of the
numbers
(I) ao i, a, 2,..., d-1
where ai is the number of the set (B) to which ai is congruent
modulo m.
If the class (I) does not contain all the numbers of the set
(B), let as be any number of the set (B) not contained in (I)
and form the following set of numbers:

(II)

aoat, oLa, 0a2a1,..., aodla,.