Fermat's Little Theorem

It is a fundamental result in number theory.

Theorem. Given a prime $p$ , for every positive integer $a \in \mathbb{N}^+$ , if $a \neq 0 \pmod p$ , then
$a^{p - 1} = 1 \quad \pmod p.$

It suffices to prove the theorem for numbers in $\mathbb{F}_p^+ \doteq \{ 1, 2, ..., p - 1\}$ .

Proof One

Define the function $f : \mathbb{F}_p^+ \rightarrow \mathbb{F}_p^+$ to be

f(x) = ax \pmod p.

For every $x \neq x' \in \mathbb{F}_p^+$ , $ax \neq ax' \mod p$ , otherwise $(x - x') \mid p$ . Hence $f$ is a bijection and

\{f(1), f(2), ..., f(p - 1)\} = \mathbb{F}_p^+.

Now we take product over all number in these two sets to obtain

(p - 1)! = \prod_{i = 1}^{p - 1} (ai) = a^{p - 1} (p - 1)! \pmod p

As $p$ is a prime, every non-zero integer has a multiplicative inverse mod $p$ . Therefore we can cancel out $(p - 1)!$ from both side and get

1 = a^{p - 1} \pmod p.

$\square$

Remark: Fermat-Euler theorem relaxes the condition of $p$ being prime. It states that $\forall p, a \in \mathbb{N}^+$ with $\gcd(a, p) = 1$ (i.e., $a$ and $p$ are coprime), we have

a^{\varphi(p)} = 1 \pmod p,

where $\varphi(p)$ is the number of elements that are coprime to $p$ in $\{1, 2, .., p - 1\}$ . When $p$ is prime, $\varphi(p) = p - 1$ .

The proof for the theorem is similar to the previous one. Let

S \subseteq \{1, 2, .., p - 1\}

be the set of numbers coprime to $p$ and define $f: S \rightarrow S$ to be

f(x) = ax \pmod p

which is a bijection. Therefore,

\prod_{x \in S} x = a^{\varphi(p)} \prod_{x \in S} x \pmod p

Cancelling out the factor $\prod_{x \in S} x$ from both side gives the desired result.

Proof Two

This proof uses the binomial expansion as follows:

\begin{aligned} (a + 1)^p &= a^p + \binom{p}{1} a^{p - 1} + ... + \binom{p}{p - 1} a + 1 &\pmod p \\ &= a^{p} + 1 &\pmod p \\ &= (a - 1)^{p} + 1 + 1 &\pmod p \\ &= ... \\ &= \begin{matrix} \underbrace{1 + 1 + ... + 1} \\ a + 1 \end{matrix} &\pmod p \\ &= a + 1 &\pmod p \end{aligned}

The second equality holds since for $1 \le i \le p - 1$ , the coefficient $\binom{p}{i} = \frac{p (p - 1) ... (p - i + 1)}{i !}$ divides $p$ , as $p$ is relative prime to all integers $1, 2, ..., i$ . The third equality follows from respectively applying the previous expansion. Finally, we get Fermat's Little Theorem by multiplying both sides of $(a + 1)^p = (a + 1) \pmod p$ by the inverse of $a + 1$ module $p$ .

Proof Three

Let $a \in \mathbb{F}_p^+$ . Consider the following numbers in $\mathbb{F}_p^+$ :

a, a^2, a^3, a^4, a^5, ...

As there are only $p - 1$ distinct numbers in $\mathbb{F}_p^+$ , it holds that there exits a smallest $h \in \mathbb{N}_+$ , such that

a^h = 1 \pmod p.

Now consider the following procedure:

$\mathcal{U} \leftarrow \mathbb{F}_p^+;$

$\mathcal{C} \leftarrow \{ \}, i \leftarrow 0$ ;

while $\mathcal{U} \neq \emptyset$ do:

$\qquad$ $i \leftarrow i + 1$ ;

$\qquad$ let $b$ be an element in $\mathcal{U}$ ;

$\qquad$ let $S_i \leftarrow \{ b, ab, a^2b, ..., a^{h - 1} b\}$ ;

$\qquad$ $\mathcal{U} \leftarrow \mathcal{U} \setminus S_i$ ;

$\qquad$ $\mathcal{C} \leftarrow \mathcal{C} \cup \{ S_i \}$ ;

Suppose that $\mathcal{C} = \{ S_1, ..., S_m \}$ . We claim that

The elements in $S_i$ are distinct. Otherwise,
$a^k b = a^\ell b \pmod p \Longrightarrow a^{k - \ell} b= 0 \pmod p,$
a contradiction. If follows that $|S_i| = h$ .
For $i \neq j$ , $S_i \cap S_j = \emptyset$ . Otherwise, let $b \in S_i \cap S_j$ . Then every element in $S_i \cup S_j$ can be expressed as $a^k b$ for some integer $k$ .

It follows that $\mathcal{C}$ is a partition of $\mathbb{F}_p^+$ . As each set in $\mathcal{C}$ has the same size, we have $h \mid (p - 1)$ and

a^{p - 1} = 1 \pmod p.

$\square$