## Fermat's little theorem

We have seen that if is a prime then divides all the binomial coefficients , . Because of this and the binomial theorem, we have

for any integers . Using mathematical induction, we have

for any integers . In particular, we can take all the 's equal to . The proves the following result.

Theorem 1.7.11 (Fermat's little theorem)   If is any integer then .

This fact was first discovered by Pierre Fermat 1.5, though he apparently gave no proof. This theorem was stated without proof by Fermat in a letter dated 1640. Leibnitz proved this in 1683 in an unpublished manuscript and Euler, in 1736, published the first proof.

Example 1.7.12   If then . Indeed, and since .

Exercise 1.7.13   Use the repeated squaring algorithm or your calculator to directly compute , , . Check that Fermat's little theorem holds in this case.

Exercise 1.7.14 (No computers allowed!)

(a) Use the division algorithm (Theorem 1.2.7) to find the remainder of modulo , where .

(b) Use the division algorithm (Theorem 1.2.7) to find the remainder of
modulo , where .

Exercise 1.7.15   Use the algorithm above to compute

(a) ,

(b) ,

(c) .

Exercise 1.7.16   Verify the divisibilty criteria for , and for in §1.3.1.

Exercise 1.7.17   Show that if is any equivalence relation on then

(a) ,

(b) if and only if ,

(c) if and only if is not equivalent to .

Exercise 1.7.18   Prove Proposition 1.7.9.

Exercise 1.7.19   Solve .

david joyner 2008-04-20