Fermat's little theorem

We have seen that if $p$ is a prime then $p$ divides all the binomial coefficients $$\left( \begin{array}{c} p \\ k \end{array}\right)$$ , $1\leq k\leq p-1$ . Because of this and the binomial theorem, we have

$$(a+b)^p\equiv a^p+b^p ({\rm mod} p),$$

for any integers $a,b$ . Using mathematical induction, we have

$$(a_1+...a_k)^p\equiv a_1^p+...+a_k^p ({\rm mod} p),$$

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

Theorem 1.7.11 (Fermat's little theorem)   If $k$ is any integer then $k^p\equiv k ({\rm mod} p)$ .

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 $p=7$ then $2^7\equiv 2 ({\rm mod} 7)$ . Indeed, $2^7=128$ and $7\vert 126$ since $126=140-14=18\cdot 7$ .

Exercise 1.7.13   Use the repeated squaring algorithm or your calculator to directly compute $3^5 ({\rm mod} 5)$ , $2^7 ({\rm mod} 7)$ , $10^11 ({\rm mod} 11)$ . 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 $1234567887654320$ modulo $m$ , where $m= 2, 3, 4, 5, 8, 9$ .

(b) Use the division algorithm (Theorem 1.2.7) to find the remainder of
$1002003004005006$ modulo $m$ , where $m= 2, 3, 4, 5, 8, 9$ .

Exercise 1.7.15   Use the algorithm above to compute

(a) $10^{11} ({\rm mod} 7)$ ,

(b) $2^{10} ({\rm mod} 3)$ ,

(c) $5^{13} ({\rm mod} 8)$ .

Exercise 1.7.16   Verify the divisibilty criteria for $4\vert a$ , $9\vert a$ and for $13\vert a$ in §1.3.1.

Exercise 1.7.17   Show that if $\sim$ is any equivalence relation on $S$ then

(a) $s\in [s]$ ,

(b) $[s]=[t]$ if and only if $s\sim t$ ,

(c) $[s]\cap [t]=\emptyset$ if and only if $s$ is not equivalent to $t$ .

Exercise 1.7.18   Prove Proposition 1.7.9.

Exercise 1.7.19   Solve $3x\equiv 7 ({\rm mod} 100)$ .