fermats-little-theorem-proof

Wed Apr 01 2026

Statement

Let pp be any prime and aa any integer not divisible by pp. Then

ap−1≡1(modp)a^{p-1} \equiv 1 \pmod{p}

There's a more general form, ap≡a(modp)a^p \equiv a \pmod{p}, which includes the trivial case when p∣ap \mid a. Both are equivalent, the second just doesn't require the coprimality condition.

Proof

Setup

Consider (Z/pZ)∗={1,2,…,p−1}(\mathbb{Z}/p\mathbb{Z})^* = \{1, 2, \ldots, p-1\} and pick some a∈Z/pZ∗a \in \mathbb{Z}/p\mathbb{Z}^*. Define a map f:Z/pZ∗→Z/pZ∗f: \mathbb{Z}/p\mathbb{Z}^* \to \mathbb{Z}/p\mathbb{Z}^* by

f(x)=a⋅xf(x) = a \cdot x

So ff sends the group elements {1,2,…,p−1}\{1, 2, \ldots, p-1\} to {a⋅1,a⋅2,…,a⋅(p−1)}\{a \cdot 1, a \cdot 2, \ldots, a \cdot (p-1)\}.

ff is a bijection

Surjective: Since pp is prime, a−1a^{-1} exists and is unique in mod  p\mod p. For any element a⋅ia \cdot i in the image, there's a pre-image a−1⋅a⋅i=ia^{-1} \cdot a \cdot i = i.

Injective: Suppose f(i)=f(j)f(i) = f(j), meaning a⋅i≡a⋅j(modp)a \cdot i \equiv a \cdot j \pmod{p}. Multiply both sides by a−1a^{-1}:

a−1⋅a⋅i≡a−1⋅a⋅j(modp)i≡j(modp)\begin{align} a^{-1} \cdot a \cdot i &\equiv a^{-1} \cdot a \cdot j \pmod{p} \\ i &\equiv j \pmod{p} \end{align}

So i≠j  ⟹  f(i)≠f(j)i \neq j \implies f(i) \neq f(j).

ff is NOT an automorphism. It doesn't preserve the group operation, i.e., f(i⋅j)≠f(i)⋅f(j)f(i \cdot j) \neq f(i) \cdot f(j). All ff does is permute the group elements.

The punchline

Since ff is a bijection on a finite set, it's just a permutation. The product of all group elements stays the same:

∏i∈Z/pZ∗i≡∏i∈Z/pZ∗f(i)(modp)∏i∈Z/pZ∗i≡∏i∈Z/pZ∗a⋅i(modp)∏i∈Z/pZ∗i≡ap−1∏i∈Z/pZ∗i(modp)1≡ap−1(modp)\begin{align} \prod_{i \in \mathbb{Z}/p\mathbb{Z}^*} i &\equiv \prod_{i \in \mathbb{Z}/p\mathbb{Z}^*} f(i) \pmod{p} \\ \prod_{i \in \mathbb{Z}/p\mathbb{Z}^*} i &\equiv \prod_{i \in \mathbb{Z}/p\mathbb{Z}^*} a \cdot i \pmod{p} \\ \prod_{i \in \mathbb{Z}/p\mathbb{Z}^*} i &\equiv a^{p-1} \prod_{i \in \mathbb{Z}/p\mathbb{Z}^*} i \pmod{p} \\ 1 &\equiv a^{p-1} \pmod{p} \end{align}

The last step cancels ∏i\prod i from both sides. Every element in (Z/pZ)∗(\mathbb{Z}/p\mathbb{Z})^* is coprime to pp, so it's invertible.

Extension to Euler's theorem

This generalizes to Euler's theorem: aφ(m)≡1(modm)a^{\varphi(m)} \equiv 1 \pmod{m} where gcd⁡(a,m)=1\gcd(a, m) = 1. Replace (Z/pZ)∗(\mathbb{Z}/p\mathbb{Z})^* with Zm∗={x∈Zm:gcd⁡(x,m)=1}\mathbb{Z}_m^* = \{x \in \mathbb{Z}_m : \gcd(x, m) = 1\}. The map f(x)=a⋅xf(x) = a \cdot x is still a bijection on this group, so the product argument carries over, just with φ(m)\varphi(m) elements instead of p−1p - 1.