Fermat's Little Theorem

We will now look at a very important theorem called Fermat's little theorem but we will first need to prove the following lemma first:

Lemma 1: Let $a, m \in \mathbb{Z}$ and let $(a, m) = 1$. Then the least residues of $a$, $2a$, …, $(m-1)a$ modulo $m$ are $1$, $2$, …, $m - 1$ in some order.

• Proof: Let $(a, m) = 1$. Then $a \not \equiv 0 \pmod m$, $2a \not \equiv 0 \pmod m$, …, $(m - 1)a \not \equiv 0 \pmod m$, so the least residues of $a$, $2a$, …, $(m-1)a$ are contained in $\{ 1, 2, ..., m - 1 \}$.

• Now assume that two of these multiples have the same least residue, call them $r, s \in \{ a, 2a, ..., (m-1)a \}$ and that $ar \equiv as \pmod m$. Since $(a, m) = 1$ we have that $r \equiv s \pmod m$. But since $r$ and $s$ are least residues we have that $0 \leq r < m$ and $0 \leq s < m$ and so we have that:

(1)

\begin{align} \quad -m < r - s < m \end{align}

• Since $r - s \equiv 0 \pmod m$ we have that $r - s$ is a multiple of $m$ restricted as above. But the only multiple of $m$ in the range above is $0$, so $r - s = 0$. Thus $r = s$.

• So the least residues of $a$, $2a$, …, $(m - 1)a$ are $1$, $2$, …, $m - 1$ in some order. $\blacksquare$

We are now ready to introduce Fermat's little theorem.

Theorem 2 (Fermat's Little Theorem): Let $a, p \in \mathbb{Z}$ and let $p$ be a prime number. Let $(a, p) = 1$. Then $a^{p-1} \equiv 1 \pmod p$.

• Proof: Let $p$ be any prime number and let $(a, p) = 1$. Then by Lemma 1 we have that the least residues of $a$, $2a$, …, $(p - 1)a$ modulo $p$ are $1$, $2$, …, $p - 1$ in some order. Then we have the following congruence:

(2)

\begin{align} \quad a \cdot (2a) \cdot ... \cdot ((p-1)a) & \equiv 1 \cdot 2 \cdot ... \cdot (p - 1) \pmod p \\ \quad (p - 1)! a^{p-1} & \equiv (p - 1)! \pmod p \end{align}

• Since $p$ is a prime number we have that $((p - 1), p) = 1$, so $((p - 1)!, p) = 1$. Hence:

(3)

\begin{align} \quad a^{p-1} \equiv 1 \pmod p \quad \blacksquare \end{align}

Let's now look at an example of applying Fermat's little theorem.

Example 1

Determine the least residue of $5^{8739} \pmod {673}$ using Fermat's little theorem.

First note that $673$ is prime and notice that $(5, 673) = 1$. Thus we can apply Fermat's little theorem to get:

(4)

\begin{align} 5^{672} \equiv 1 \pmod {673} \end{align}

Using the division algorithm, let's find the remainder when 8739 is divided by 672:

(5)

\begin{equation} 8739 = 672(13) + 3 \end{equation}

Thus we can obtain the congruence:

(6)

\begin{align} 5^{8739} & \equiv 5^{672(13) + 3} \pmod {673} \\ 5^{8739} & \equiv (5^{672})^{13} (5^3) \pmod {673} \\ 5^{8739} & \equiv 1^{13}(5^3) \pmod {673} \\ 5^{8739} & \equiv 5^3 \pmod {673} \\ 5^{8739} & \equiv 125 \pmod {673} \end{align}

Thus the least residue $5^{8739}$ modulo $673$ is $125$.