# Fermat’s Little Theorem

Introduction

This is a beautiful theorem which states that the difference between a positive integer $a$ and a prime power of $a$, $a^p-a$, is divisible by $p$. It’s history can be found in Wikipedia: Fermat posited the theorem (and as usual, did not give the proof) while Euler first published a proof using mathematical induction. Below, we will state the theorem and provide a simple-to-understand proof using only modular arithmetic, followed by another simple proof using mathematical induction.

Statement

For an integer $a$ and a prime $p$, the following is true:

$\displaystyle a^{p} \equiv a\mod{p}\ \ \ \ (1)$

Proof

Note that if $a\equiv 0\mod{p}$, the statement is trivially true. Therefore, we focus on the case that $a\not \equiv 0 \mod{p}$, that is, $a$ is a positive integer such that $p$ does not divide $a$. (This also implies that $a\neq 0$.) In that case, we can divide both side of the main statement by $a$ and have the following statement:

$a^{p-1}\equiv 1\mod{p}\ \ \ \ (2)$

Proving the above statement will complete the proof.

When we divide $a$ with prime $p$, the remainder must be one of $1,2,3,\cdots , p-1$. Therefore, one of the following congruences must be true:

$a\equiv 1\mod{p}$

$a\equiv 2\mod{p}$

$\vdots$

$a\equiv (p-1)\mod{p}$

Now consider the numbers $s_k=k\cdot a, 1\leq k \leq p-1$. These numbers are $1\cdot a, 2\cdot a, 3\cdot a, \cdots , (p-1)\cdot a$. We ask the following question: is it possible that two different numbers $s_i$ and $s_j$ be congruent modulo $p$? Let us find out. (Hint: we are going to use contradiction.)

Suppose when $x\neq y$, we have $s_x=x\cdot a$ and $s_y=y\cdot a$ such that $0\leq x,y\leq p-1, x\neq y$ and yet $s_i\equiv s_j\mod{p}$. Since $x,y \leq p-1$ and $x\neq y$, it follows that

$\displaystyle x\not \equiv y\mod{p}\ \ \ \ (3)$

Next, we have, due to our assumption, that

$\begin{array}{lrcl} & s_x &\equiv & s_y\mod{p}\\ \implies & xa &\equiv & ya\mod{p}\\ \implies & (x-y)a &\equiv & 0\mod{p}\\ \implies & x-y &\equiv & 0\mod{p}\text{ since }a\not \equiv 0\mod{p}\\ \implies & x &\equiv & y\mod{p} \end{array}$

which contradicts $(3)$. This implies, if $i\neq j$, $s_i \neq s_j, 1\leq i,j\leq p-1$. Therefore each $s_k,1\leq k\leq p-1$ is congruent to a unique number $u, 1\leq u\leq p-1$. Thus the sequence of all numbers

$\displaystyle (1\cdot a)\mod{p},(2\cdot a)\mod{p},(3\cdot a)\mod{p},\cdots \left((p-1)\cdot a\right)\mod{p}$

is nothing but a rearrangement of the numbers

$\displaystyle 1,2,3,\cdots ,(p-1)\,.$

Therefore,
$\begin{array}{lrcl} & (1\cdot a)(2\cdot a)(3\cdot a)\cdots \left((p-1)\cdot a\right) &\equiv & 1\cdot 2\cdot 3\cdots (p-1) \mod{p}\\ \implies & (p-1)!a^{p-1}&\equiv & (p-1)!\mod{p}\\ \end{array}$

Since $p\geq 2 \implies (p-1)!\neq 0$, by dividing both sides by $(p-1)!$ it follows that

$\displaystyle a^{p-1} \equiv 1\mod{p}$.

$\square$

A Proof by Induction

We will prove that for a given prime $p$, the following statement is true for all natural number $a$ such that $p$ does not divide $a$:

$a^{p-1}\equiv 1\mod{p}\ \ \ \ (2)$

(Basis)

When $a=1$, the statement trivially holds since $p \geq 2$.

(Inductive Hypothesis)

Suppose the above statement is true for $1\leq a\leq n-1$. That is,

$(n-1)^{p-1}\equiv 1\mod{p}$ where $p \nmid (n-1)$. This implies,

$(n-1)^p\equiv (n-1)\mod{p}$.

(Induction)

We need to prove that $n^{p-1} \equiv 1\mod{p}$ where $p \nmid n$.

Now there can be two cases depending on whether $p$ divides  $n-1$.

[Case 1] $n-1\not \equiv 0\mod{p}$

In this case, we can use the inductive hypothesis: $(n-1)^{p-1} \equiv 1 \mod{p}$.

Then,

$\begin{array}{rlll} & n^{p} &=& \left(1+(n-1)\right)^{p}\\ & &=& 1 + \underbrace{p(n-1) + \frac{p(p-1)}{2!}(n-1)^2 + \cdots }_{\text{multiples of }p} + (n-1)^{p}\\ & &\equiv & 1 + (n-1)^{p} \mod{p}\\ & &\equiv & 1 + (n-1) \mod{p} \ \ \ \ \text{[by using the inductive hypothesis]}\\ & &\equiv & n\mod{p}\,.\\ \end{array}$
Since $n\not \equiv 0\mod{p}$, we can divide both sides by $n$ and thus arrive at
$n^{p-1} \equiv 1\mod{p}$.

Now the second case.

[Case 2] $n-1 \equiv 0\mod{p}$

If $p$ divides $n-1$, then
$\begin{array}{rlll} & n-1\equiv 0 \mod{p}\\ \implies & n \equiv 1 \mod{p}\\ \implies & n^{p-1} \equiv 1\mod{p} \ \ \ \ \text{since }p\geq 2 \,. \end{array}$

Therefore, for all primes $p$ and natural numbers $n\not \equiv 0\mod{p}$,  the following statement holds:
$n^{p-1}\equiv 1\mod{p}$.

$\square$

## 3 thoughts on “Fermat’s Little Theorem”

1. As far as I can remember, there is also a nice combinatorial proof for this theorem 🙂

Suppose we are making necklaces from beads. Each bead can be one of $k$ colors. Since we have no restriction on colors, there can be $k^p$ different bead-strings of length $p$. Of these, only $k$ strings are single-colored. Let’s take them out: now we have $k^p-k$ strings left. Now let’s join the two ends of each of these strings to make a necklace. How many of these necklaces are unique? Only
$\displaystyle \frac{k^p-k}{p},$
because every unique necklace can be generated from $p$ different strings. Since the cardinality of any set is an integer, the cardinality of the set “unique non-monochromatic necklaces containing $p$ beads, each bead having one of $k$ colors” is also an integer. This implies that $\frac{k^p-k}{p}$ is an integer, or equivalently, ${k^p-k}$ is a multiple of $p$.