Fermat's Little Theorem

In this post we prove Fermat’s little theorem.

Let \(p\) be a prime number. Then, for any integer \(a\) the number \(a^p-a\) is divisible by \(p\). This can also be expressed in congruence notation as

\[a^p \equiv a \quad (\text{mod}\ p)\]

or equivalently, by subtracting \(a\) from both sides,

\[a^p -a \equiv 0 \quad (\text{mod}\ p)\]

For the proof it’s sufficient to consider only non-negative values of \(a\). If \(p=2\), we have \((-a)^2-(-a) = a^2+a\), and we are back at positive numbers. For odd values of \(p\), we find \((-a)^p-(-a) = -a^p-(-a) = -(a^p-a)\). Therefore, if \(a^p-a\) is divisible by \(p\), so is its negative, \(-(a^p-a)\), and therefore it’s sufficient to show that \(a^p-a\) is divisible by \(p\).

Proof by induction

First, we verify the statement for \(a=0\). We have \(0^p-0\equiv0\ (\text{mod}\ p)\).

For the induction step we assume that the theorem holds for some integer \(a\). We aim to show that it also holds for \(a+1\), meaning we show that

\[(a+1)^p \equiv a+1 \quad (\text{mod}\ p)\]

Expanding \((a+1)^p\) using the binomial theorem, we get

\((a+1)^p = a^p + \binom{p}{1}a^{p-1} + \dots + \binom{p}{p-1}a + 1\) Each binomial coefficient can be written as

\[\binom{p}{k} = \frac{p!}{(p-k)!\cdot k!} = \frac{p\cdot (p-1)\cdot \ldots \cdot (p-k+1)}{1\cdot 2\cdot \ldots \cdot k}\]

Each term with a binomial coefficient has a factor \(p\) in the numerator. Since \(p\) is prime it is not divisible by any factor in the denominator and therefore each term with a binomial coefficient is divisible by \(p\). It follows

\[(a+1)^p = a^p + \binom{p}{1}a^{p-1} + \dots + \binom{p}{p-1}a + 1 \equiv a^p+1 \quad (\text{mod}\ p)\]

Subtracting \(a+1\) from both sides gives

\[\begin{align} (a+1)^p -(a+1) & \equiv a^p+1-(a+1) \quad (\text{mod}\ p) \\[1.5em] & \equiv a^p-a \quad (\text{mod}\ p) \end{align}\]

By the induction hypothesis, we know that \(a^p-a\equiv0\ (\text{mod}\ p)\). Hence, it follows that \((a+1)^p-(a+1)\equiv0\ (\text{mod}\ p)\), proving that the theorem holds for \(a+1\) and, by induction, for all \(a\geq 0\) (and all negative values of \(a\) as stated at the beginning).

Proof of the equivalent \(a^{p-1}\equiv\ 1\ (\text{mod}\ p)\)

If \(p\) is prime and does not divide \(a\), Fermat’s little theorem is equivalent to

\[a^{p-1} \equiv 1 \quad (\text{mod}\ p)\]

Proof: If \(p\) is prime and does not divide \(a\) it follows \(\gcd(a, p)=1\). Then, due to Bézout’s Identity there must exist two integers \(x\) and \(y\) such that

\[ax+py=1\]

If we divide both sides by \(p\) we get the same remainder. Therefore,

\[ax+py \equiv 1 \quad (\text{mod}\ p)\]

Since \(py\) is a multiple of \(p\) we have

\[ax \equiv 1 \quad (\text{mod}\ p)\]

and it follows that there must be an multiplicative inverse \(x = a^{-1}\) of \(a\) which, when multiplied with \(a\), gives \(1\). Because this inverse exists, we can multiply it to both sides of the equation \(a^p\equiv a\ (\text{mod}\ p)\) from the beginning and get

\[a^{p}\cdot a^{-1} \equiv a\cdot a^{-1} \quad (\text{mod}\ p)\] \[a^{p-1} \equiv 1 \quad (\text{mod}\ p)\]