Advanced High-School Mathematics

86 CHAPTER 2 Discrete Mathematics

a^6 =

∑^6

k=0

Ñ

6

k

é

(7q)kr^6 −k≡r^6 (mod 7).

This reduces matters to only six easily verifiable calculations:

16 ≡1(mod 7), 26 ≡1(mod 7), 36 ≡1(mod 7),

46 ≡(−3)^6 ≡1(mod 7), 56 ≡(−2)^6 ≡1(mod 7), 66 ≡(−1)^6 ≡1(mod 7).

In other words, for any integer a not divisible by 7, we have ap−^1 ≡
1(mod 7).

In order to generalize the above result, we shall first make the fol-
lowing observation, namely that ifxandyare arbitrary integers, and
ifpis a prime number, then using exercise 9 on page 62 we get

(x+y)p ≡

∑p

k=0

Ñ

p

k

é

xkyp−k

≡ xp+yp(modp).

That is to say, for any integersxandy and any prime numberp, we
have

(x+y)p≡xp+yp(modp).

Theorem. (Fermat’s Little Theorem)Letpbe a prime number. Then
for all integersanot divisible bypwe have

ap−^1 ≡1(modp).

Proof. There are a number of proofs of this fact;^17 perhaps the most
straightforward is based on the Binomial Theorem together with the

(^17) It is interesting to note that while Fermat first observed this result in a letter in 1640, the first
known complete proof was not given until 1736 by Leonard Euler.