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

CHAPTER V.

PRIMITIVE ROOTS MODULO m~32. EXPONENT OF AN INTEGER MODULO m
Let
al,.., a2,.,m) (A)
be the set of )(m) positive integers not greater than m and
prime to m; and let a denote any integer of the set (A). Now
any positive integral power of a is prime to m and hence is
congruent modulo m to a number of the set (A). Hence,
among all the powers of a there must be two, say a" and a",
n>v, which are congruent to the same integer of the set (A).
These two powers are then congruent to each other; that is,
an= a mod m.
Since a" is prime to m the members of this congruence may be
divided by a". Thus we have
n -v I mod m.
That is, among the powers of a there is one at least which is
congruent to i modulo m.
Now, in the set of all powers of a which are congruent to
i modulo m there is one in which the exponent is less than in
any other of the set. Let the exponent of this power be d,
so that ad is the lowest power of a such that
ad= I mod m.
61