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

48

THEORY OF NUMBERS

ber by member and divide each member of the resulting congruence by al-a2... ao$(m) (which is prime to m), we have
ao(m)- i mod m.
This result is known as Fermat's general theorem. It may
be stated as follows:
If m is any positive integer and a is any integer prime to m,
then
ao(m) = mod m.
COROLLARY i. If a is any integer not divisible by a prime
number p, then
a-1 i mod p.
COROLLARY 2. If p is any prime number and a is any
integer, then
ap =a mod p.
~ 24. EULER'S PROOF OF THE SIMPLE FERMAT THEOREM
The theorem of. Cor. i, ~ 23, is often spoken of as the simple
Fermat theorem. It was first announced by Fermat in I679,
but without proof. The first proof of it was given by Euler
in I736. This proof may be stated as follows:
From the Binomial Theorem it follows readily that
(a+ I)P-aP+ mod p
since
p!
o<r<p,
r!(p-r)!'
is obviously divisible by p. Subtracting a+i from each side
of the foregoing congruence, we have

(a+ I)P- (a+ i) a'- a mod p.