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}