## 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:

$$a^p \equiv a\pmod{p}$$

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$$:

$$a \equiv 1 \pmod{p} \iff a^p \equiv 1 \pmod{p}$$

### $$a > p$$:

$$a \equiv 0 \pmod{p} \iff a^p \equiv 0 \pmod{p}$$

$$a \equiv 1 \pmod{p} \iff a^p \equiv 1 \pmod{p}$$

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:

$$|S| = a^p$$

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:

$$|S_0| = a$$

$$|S_1| = |S| - |S_0| = a^p - a$$

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:

$$a^p - a \equiv 0 \pmod{p}$$

## A combinatorial proof via the binomial theorem:

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

$$1^p \equiv 1 \pmod{p}$$

is certainly true.

Now, let’s suppose that for our inductive step

$$a^p \equiv a \pmod{p}$$

is assumed to be true.

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

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

Now, given that:

$${p \choose k} = \frac{p!}{k!(p-k)!}$$

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

$$(a+1)^p \equiv a^p + 1 \pmod{p}$$

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

$$(a+1)^p \equiv a + 1 \pmod{p}$$

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}$$,

$$ux \equiv uy \pmod{p}$$

implies that:

$$x \equiv y \pmod{p}$$

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

$$u \cdot (x-y) \equiv 0 \pmod{p}$$

$$u \equiv 1 \pmod{p}$$

then we have:

$$(x-y) \equiv 0 \pmod{p}$$

### 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]$$,

$$l \cdot a \equiv m \cdot a \pmod{p} \iff l \equiv m \pmod{p}$$

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:

$$a^{p-1} \cdot (p-1)! \equiv (p-1)! \pmod{p}$$

and by the cancellation law:

$$a^{p-1} \equiv 1 \pmod{p}$$