Fermat’s little theorem:

If $$p$$ is a prime number then for any integer $$a$$, the number $$a^p-a$$ is an integer multiple of $$p$$. Using modular arithmetic, this relation may be expressed as follows:

\begin{equation} a^p \equiv a\pmod{p} \end{equation}

While it is called ‘little theorem’, this theorem due to Fermat is actually a pretty big deal as it is the basis for important primality tests such as the Miller-Rabin test and even the RSA-encryption standard. For this reason, it is worth going through several proofs of this theorem in order to develop a good understanding of its implications.

A couple intuitions for Fermat’s little theorem:

Let’s consider two cases.

$$a \leq p$$:

\begin{equation} a \equiv 1 \pmod{p} \iff a^p \equiv 1 \pmod{p} \end{equation}

$$a > p$$:

\begin{equation} a \equiv 0 \pmod{p} \iff a^p \equiv 0 \pmod{p} \end{equation}

\begin{equation} a \equiv 1 \pmod{p} \iff a^p \equiv 1 \pmod{p} \end{equation}

and from this we may infer that $$a^p \equiv a\pmod{p}$$. But, in order to make the chain of arguments more precise we shall consider three different proofs.

A combinatorial proof via necklaces:

Let’s suppose we have an alphabet of $$a \in \mathbb{N}$$ symbols which we use to construct a necklace of length $$p \in \mathbb{P}$$. Without loss of generality, let’s suppose that each necklace among this set of necklaces $$S$$ is oriented clockwise so there is a unique geodesic that serves as the shortest path between any pair of distinct beads in a necklace.

A simple counting argument may suffice to demonstrate that:

\begin{equation} |S| = a^p \end{equation}

Moreover, if we identify the necklaces with a single symbol with $$S_0$$ and the necklaces with more than one symbol with $$S_1$$ then a simple counting argument suffices to demonstrate that:

\begin{equation} |S_0| = a \end{equation}

\begin{equation} |S_1| = |S| - |S_0| = a^p - a \end{equation}

Now, if we can break up each $$s \in S_1$$ into repeating copies of a string $$l$$ then the length of $$l$$ must divide the length of $$s$$. However, since the length of $$s$$ is prime the only possible length of $$l$$ is $$p$$. In fact, given that there are $$p$$ distinct ways to shift a particular bead clockwise for any necklace $$s \in S_1$$, there are $$p$$ equivalent representations of $$s$$ in $$S_1$$.

It follows that:

\begin{equation} a^p - a \equiv 0 \pmod{p} \end{equation}

A combinatorial proof via the binomial theorem:

Let’s suppose we fix $$p \in \mathbb{P}$$. The $$n=1$$ case

\begin{equation} 1^p \equiv 1 \pmod{p} \end{equation}

is certainly true.

Now, let’s suppose that for our inductive step

\begin{equation} a^p \equiv a \pmod{p} \end{equation}

is assumed to be true.

Using the binomial theorem, we may proceed by induction as follows:

\begin{equation} (a+1)^p = \sum_{k=0}^p {p \choose k} a^{p-k} \end{equation}

Now, given that:

\begin{equation} {p \choose k} = \frac{p!}{k!(p-k)!} \end{equation}

for $$1 \leq k \leq p-1$$, $$p$$ divides the numerator but not the denominator. It follows that:

\begin{equation} (a+1)^p \equiv a^p + 1 \pmod{p} \end{equation}

Finally, given the assumption that $$a^p \equiv a \pmod{p}$$, we may confirm the correctness of the inductive step:

\begin{equation} (a+1)^p \equiv a + 1 \pmod{p} \end{equation}

which concludes the proof.

A proof of Fermat’s little theorem via modular arithmetic:

Lemma 1: the cancellation law

If $$u,x$$ and $$y$$ are integers and $$u \equiv 1 \pmod{p}$$,

\begin{equation} ux \equiv uy \pmod{p} \end{equation}

implies that:

\begin{equation} x \equiv y \pmod{p} \end{equation}

and the reason for this is that if the following equations hold:

\begin{equation} u \cdot (x-y) \equiv 0 \pmod{p} \end{equation}

\begin{equation} u \equiv 1 \pmod{p} \end{equation}

then we have:

\begin{equation} (x-y) \equiv 0 \pmod{p} \end{equation}

Lemma 2: the rearrangement property

The sequence $$\{k \cdot a\}_{k=1}^{p-1}$$ when reduced modulo $$p$$ becomes a rearrangement of $$[1,p-1]$$ since $$\forall l, m \in [1,p-1]$$,

\begin{equation} l \cdot a \equiv m \cdot a \pmod{p} \iff l \equiv m \pmod{p} \end{equation}

by the cancellation law. Therefore, (6) holds if and only if $$l=m$$.

Proof:

By the rearrangement property, the sequence $$\{k \cdot a\}_{k=1}^{p-1}$$ when reduced modulo $$p$$ becomes a rearrangement of $$[1,p-1]$$. Therefore, we must have:

\begin{equation} a^{p-1} \cdot (p-1)! \equiv (p-1)! \pmod{p} \end{equation}

and by the cancellation law:

\begin{equation} a^{p-1} \equiv 1 \pmod{p} \end{equation}