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$