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.9 (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.10   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.11   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.12 (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.13   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.14   Verify the divisibilty criteria for $4\vert a$, $9\vert a$ and for $13\vert a$ in §1.3.1.

Exercise 1.7.15   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.16   Prove Proposition 1.7.7.

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