Fermat's Little Theorem

⚡ Key Takeaways

Fermat's Little Theorem: If $p$ is prime and $a$ is not divisible by $p$ , then $a^{p-1} \equiv 1 \pmod{p}$ . Equivalently, $a^p \equiv a \pmod{p}$ for every integer $a$ . Key result in words: raising any integer to the $p$ -th power leaves it unchanged modulo a prime $p$ . Where it applies: modular arithmetic, primality testing, cryptography (RSA), and the structure of the multiplicative group $(\mathbb{Z}/p\mathbb{Z})^\times$ . Who/when: stated by Pierre de Fermat in 1640; first published proof by Leonhard Euler, 1736.

💡 The Core Insight

In the world of arithmetic modulo a prime $p$ , multiplying every nonzero residue $\{1, 2, \dots, p-1\}$ by a fixed nonzero element $a$ merely permutes that set. Permutations preserve products, so the product of all elements equals the product of all elements times $a^{p-1}$ . Cancelling the (invertible) product forces $a^{p-1} \equiv 1$ . The primality of $p$ is exactly what guarantees that nonzero residues can be cancelled — that $\mathbb{Z}/p\mathbb{Z}$ is a field.

DefinitionCongruence Modulo n

For integers $a$ , $b$ and a positive integer $n$ , we write $a \equiv b \pmod{n}$ (" $a$ is congruent to $b$ modulo $n$ ") iff $n$ divides $a - b$ . The set of integers congruent to $a$ modulo $n$ is the residue class $[a]_n$ . Modular arithmetic is well-defined: if $a \equiv a'$ and $b \equiv b'$ , then $a+b \equiv a'+b'$ and $ab \equiv a'b'$ .

TheoremFermat's Little Theorem

Let $p$ be a prime. Then for every integer $a$ with $p \nmid a$ , equation [1] holds. Equivalently, for every integer $a$ whatsoever, equation [2] holds. Moreover, the order $\mathrm{ord}_p(a)$ of $a$ modulo $p$ — the least positive $k$ with $a^k \equiv 1$ — divides $p-1$ .

3

\quad \mathrm{ord}_p(a) \mid (p-1).

Derivation hint: by the division algorithm write $p-1 = q\cdot\mathrm{ord}_p(a) + r$ with $0 \le r < \mathrm{ord}_p(a)$ ; then $a^r \equiv 1$ forces $r = 0$ by minimality of the order.

TheoremEuler's Generalization

For any modulus $n \ge 1$ and any integer $a$ coprime to $n$ ,

4

\quad a^{\varphi(n)} \equiv 1 \pmod{n},

where $\varphi$ is Euler's totient function, $\varphi(n) = |\{1 \le k \le n : \gcd(k,n)=1\}|$ . FLT is the special case $n = p$ prime, since $\varphi(p) = p-1$ . Derivation hint: replace the full residue system $\{1,\dots,p-1\}$ in the proof below by the reduced residue system of units modulo $n$ , which has size $\varphi(n)$ .

ProofProof via Rearrangement of Residues

We prove form [1]. Fix a prime $p$ and an integer $a$ with $p \nmid a$ .

Step 1. Consider the set of nonzero residues $S = \{1, 2, \dots, p-1\}$ . Form the products $a\cdot 1,\, a\cdot 2,\, \dots,\, a\cdot(p-1)$ and reduce each modulo $p$ .

Step 2. No product is $\equiv 0$ . Since $p$ is prime and $p \nmid a$ and $p \nmid k$ for $1 \le k \le p-1$ , we have $p \nmid ak$ (Euclid's lemma). So each $ak \bmod p$ lies in $S$ .

Step 3. The products are distinct. If $ai \equiv aj \pmod p$ , then $p \mid a(i-j)$ ; since $p \nmid a$ , $p \mid (i-j)$ , forcing $i = j$ for $i,j \in S$ . Hence the map $k \mapsto ak \bmod p$ is injective on a finite set, thus a bijection of $S$ onto itself — a permutation.

Step 4. Because multiplication is commutative, the product of all the $ak$ equals the product of all elements of $S$ :

5

\quad \prod_{k=1}^{p-1} (a k) \equiv \prod_{k=1}^{p-1} k \pmod{p}.

Derivation hint: Step 3 says the left product runs over the same set of residues, merely reordered.

Step 5. Factor out $a$ from each of the $p-1$ terms on the left:

6

\quad a^{p-1} \cdot (p-1)! \equiv (p-1)! \pmod{p}.

Derivation hint: $\prod_{k=1}^{p-1}(ak) = a^{p-1}\prod_{k=1}^{p-1}k = a^{p-1}(p-1)!$ .

Step 6. Since $p$ is prime, $\gcd((p-1)!, p) = 1$ — no factor of $(p-1)!$ is divisible by $p$ . Therefore $(p-1)!$ is invertible modulo $p$ and may be cancelled, yielding

7

\quad a^{p-1} \equiv 1 \pmod{p}. \qquad \blacksquare

Derivation hint: cancel the unit $(p-1)!$ from both sides of [6]; cancellation is legitimate precisely because $\mathbb{Z}/p\mathbb{Z}$ is a field.

∎

mathematician · Pierre de Fermat | 1607–1665

A magistrate at the parlement of Toulouse, Fermat pursued mathematics as an avocation yet helped found number theory, analytic geometry, probability, and the calculus of maxima and minima. He communicated results in letters — typically without proofs. In a letter of 18 October 1640 to Bernard Frénicle de Bessy he stated what we now call his Little Theorem, remarking he would send the proof "if it were not so long." That proof, if it existed, was never recorded; Euler supplied the first published demonstration nearly a century later. Fermat's habit of stating theorems without proof also produced his far harder Last Theorem ( $x^n + y^n = z^n$ has no positive integer solutions for $n>2$ ), resolved only by Wiles in 1994.

🧠 Intuition

Think of the nonzero residues mod $p$ as beads on a circular bracelet. "Multiply everything by $a$ " is a shuffle that picks up each bead and drops it in another slot — but it never collapses two beads together and never sends one to the empty (zero) slot. Because it's a clean reshuffle (a permutation), the collection of beads is unchanged; only the labels moved. The total product of bead-labels is therefore the same before and after, and the only difference between "before" and "after" is the factor of $a$ that got multiplied in $p-1$ times. So that accumulated factor $a^{p-1}$ must be invisible — i.e., $\equiv 1$ . The primality of $p$ is what forbids two beads from merging: in $\mathbb{Z}/6\mathbb{Z}$ , multiplying by $2$ sends both $3$ and $0$ toward collisions because $6$ is composite, and the bracelet trick fails.

Figure

Multiplication by

a=3

permutes the nonzero residues modulo

p=7

, the geometric heart of the proof.

ExampleReducing a Huge Power

Given: Compute $2^{1000000} \bmod 7$ .

Step 1. $7$ is prime and $7 \nmid 2$ , so FLT gives $2^{6} \equiv 1 \pmod 7$ . (Check: $2^6 = 64 = 9\cdot 7 + 1$ .)

Step 2. Reduce the exponent modulo $p-1 = 6$ : $1000000 = 6 \cdot 166666 + 4$ , so $1000000 \equiv 4 \pmod 6$ .

Step 3. Therefore

9

\quad 2^{1000000} = \big(2^{6}\big)^{166666}\cdot 2^{4} \equiv 1^{166666}\cdot 2^4 \equiv 16 \pmod 7.

Derivation hint: split the exponent using $2^6 \equiv 1$ , then evaluate the residual $2^4$ .

Step 4. $16 = 2\cdot 7 + 2$ , so $16 \equiv 2$ .

\boxed{2^{1000000} \equiv 2 \pmod 7}

ExampleModular Inverse via FLT

Given: Find the multiplicative inverse of $a = 5$ modulo $p = 13$ .

Step 1. Since $13$ is prime and $13 \nmid 5$ , FLT gives $5^{12}\equiv 1$ , hence $5\cdot 5^{11}\equiv 1$ . So the inverse is $5^{11}\bmod 13$ .

10

\quad a^{-1} \equiv a^{p-2} \pmod{p}.

Derivation hint: $a\cdot a^{p-2} = a^{p-1}\equiv 1$ , so $a^{p-2}$ is the inverse.

Step 2. Compute $5^{11}\bmod 13$ by repeated squaring: $5^2 = 25 \equiv 12 \equiv -1$ . Then $5^4 \equiv (-1)^2 = 1$ , $5^8 \equiv 1$ .

Step 3. $5^{11} = 5^{8}\cdot 5^{2}\cdot 5^{1} \equiv 1\cdot(-1)\cdot 5 = -5 \equiv 8 \pmod{13}$ .

Step 4. Verify: $5\cdot 8 = 40 = 3\cdot 13 + 1 \equiv 1$ . ✓

\boxed{5^{-1} \equiv 8 \pmod{13}}

⚠️ The Converse Is False

The implication runs prime ⟹ congruence, not the reverse. From " $a^{n-1}\equiv 1 \pmod n$ for some particular $a$ " you cannot conclude that $n$ is prime. Composite numbers can satisfy the Fermat congruence for many bases; those that satisfy it for one base are Fermat pseudoprimes to that base, and those satisfying it for all coprime bases are Carmichael numbers. Also note the coprimality requirement in form [1]: if $p \mid a$ then $a^{p-1}\equiv 0$ , not $1$ — use form [2] instead, which is unconditional.

CounterexampleCarmichael Number 561

Take $n = 561 = 3\cdot 11\cdot 17$ , which is composite. Yet for every integer $a$ coprime to $561$ ,

11

\quad a^{560} \equiv 1 \pmod{561}.

Derivation hint: $560$ is divisible by $2,10,16$ — the values of $p-1$ for $p=3,11,17$ — so FLT holds modulo each prime factor, and the Chinese Remainder Theorem combines them. A naive "Fermat test" with random bases would repeatedly declare $561$ "probably prime." Carmichael numbers ( $561, 1105, 1729, \dots$ ) are infinite in number (Alford–Granville–Pomerance, 1994), which is why the strong (Miller–Rabin) test, not the plain Fermat test, is used in practice.

connection

FLT is the prime case of Euler's Theorem via the Euler Totient Function, and both are corollaries of Lagrange's Theorem (Group Theory) applied to the unit group $(\mathbb{Z}/n\mathbb{Z})^\times$ : an element's order divides the group order. The structure theorem that $(\mathbb{Z}/p\mathbb{Z})^\times$ is cyclic sharpens FLT — it guarantees a Primitive Root of order exactly $p-1$ . The induction proof exposes the Freshman's Dream identity $(a+b)^p \equiv a^p + b^p \pmod p$ , a hallmark of the Frobenius Endomorphism in fields of characteristic $p$ . FLT also underpins Wilson's Theorem (via $(p-1)! \equiv -1$ ), the Chinese Remainder Theorem when gluing congruences, and the theory of Quadratic Residues through Euler's criterion $a^{(p-1)/2}\equiv \left(\tfrac{a}{p}\right)$ .

🔬 Where this appears

⏳ History

- 1640 — Pierre de Fermat states the theorem in a letter to Frénicle de Bessy, motivated by his study of perfect numbers and Mersenne primes; he omits the proof.

- 1736 — Leonhard Euler publishes the first proof, Theorematum quorundam ad numeros primos spectantium demonstratio, using a binomial/induction argument.

- 1750s–1763 — Euler generalizes to composite moduli, introducing the totient

\varphi(n)

and proving Euler's theorem [4].

- 1770–1771 — Lagrange and Wilson context: Lagrange proves Wilson's theorem, tightly connected to FLT and

(p-1)!

.

- 1801 — Gauss, in Disquisitiones Arithmeticae, systematizes congruence notation

\equiv

and recasts FLT within the algebra of residue classes.

- 1801 — Gauss proves the existence of primitive roots, showing

(\mathbb{Z}/p\mathbb{Z})^\times

is cyclic, refining FLT's order statement [3].

- 1910 — Robert Carmichael identifies the absolute pseudoprimes (Carmichael numbers), exposing the failure of the Fermat test's converse.

- 1976–1980 — Miller and Rabin develop the strong probabilistic primality test grounded in Fermat-type identities.

- 1994 — Alford, Granville, and Pomerance prove there are infinitely many Carmichael numbers.

open-problem

While FLT itself is settled, the boundary questions it spawns remain rich and partly open. Fermat quotients $q_p(a) = \frac{a^{p-1}-1}{p} \bmod p$ encode finer information; primes with $q_p(2)\equiv 0$ are Wieferich primes, and only two ( $1093$ and $3511$ ) are known — whether infinitely many exist is open, and surprisingly, this connects to the first case of Fermat's Last Theorem. The distribution of bases for which a composite $n$ passes the Fermat test, the density of Carmichael numbers, and the exact strength of the Artin conjecture (that a given non-square integer is a primitive root for infinitely many primes — unproven unconditionally) all probe how sharply FLT's converse fails. Algorithmically, whether deterministic polynomial-time primality (achieved by AKS, 2002) can be made as fast as the Fermat-based probabilistic tests in practice remains a live engineering frontier.

Formal Statement

Why It Holds / Derivation

Building Intuition

Worked Examples

Common Misconceptions

Connections

Real-World Applications

Historical Development

Subtleties & Limits

See Also