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

62

THEORY OF NUMBERS

We shall now show that if aa= i mod m, then a is a multiple
of d. Let us write
a=d8+-3, o.<,<d.
Then
aa I mod m, (2)
ad= i mod m, (3)
the last congruence being obtained by raising (i) to the power
6. From (3) we have
ad +_ a mrod m;
or
a = i mod m.
Hence /3=o, for otherwise d is not the exponent of the lowest
power of a which is congruent to i modulo m. Hence d is a
divisor of a.
These results may be stated as follows:
I. If m is any integer and a is any integer prime to m, then
there exists an integer d such that
ad I mod m
while there is no integer 3 less than d for which
a= i mod m.
Further, a necessary and sufficient condition that
av= i mod m
is that v is a multiple of d.
DEFINITION. The integer d which is thus uniquely determined when the two relatively prime integers a and m are given
is called the exponent of a modulo m. Also, d is said to be
the exponent to which a belongs modulo m.
Now, in every case we have

a+(m) I, a(m) i mod m,