Fermat's Little Theorem

Fermat's Little Theorem (FLT — not to be confused with Fermat's Last Theorem) is one of the foundational results of elementary number theory. Precisely, it asserts that for a prime $p$ and any integer $a$ coprime to $p$, the residue $a^{p-1}$ equals $1$ modulo $p$. This matters because it gives an immediate, computable constraint on the powers of any nonzero residue class, revealing that the multiplicative group modulo a prime has a rigid cyclic structure where every element's order divides $p-1$. It is the engine behind fast modular exponentiation tricks, the Fermat primality test, and the correctness of RSA encryption. The surprising fact: despite involving exponentials, the theorem reduces a seemingly intractable computation like $2^{1000000}\mathrm{mod}7$ to a trivial one, and it holds with no exceptions whatsoever — provided $p$ is genuinely prime.

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.

Formal Statement

Congruence Modulo n

For integers $a$, $b$ and a positive integer $n$, we write $a\equiv b(\mathrm{mod}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^{\prime }$ and $b\equiv b^{\prime }$, then $a+b\equiv a^{\prime }+b^{\prime }$ and $ab\equiv a^{\prime }{b}^{\prime }$.

The theorem has two equivalent standard forms.

Here the symbols are: $p$ a prime number; $a$ an arbitrary integer; $\gcd (a,p)$ the greatest common divisor; and $\equiv (\mathrm{mod}p)$ denotes congruence modulo $p$.

Fermat'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$.

Euler's Generalization

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

Why It Holds / Derivation

Proof via Rearrangement of Residues

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

:::proof[Alternative Proof via Induction (form [2])] We show $a^p\equiv a(\mathrm{mod}p)$ for all integers $a\ge 0$ by induction; negative $a$ and the coprime form follow.

For $1\le k\le p-1$, the binomial coefficient $\left(\genfrac{}{}{0ex}{}{p}{k}\right)=\frac{p!}{k!(p-k)!}$ is divisible by $p$, because $p$ divides the numerator $p!$ but not the denominator $k!(p-k)!$ (all factors are $<p$, and $p$ is prime). Hence the sum vanishes modulo $p$, giving $(a+1{)}^p\equiv a^p+1\equiv a+1(\mathrm{mod}p)$, completing the induction. $■$

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.

Building 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.

Multiplication by $a=3$ permutes the nonzero residues modulo $p=7$, the geometric heart of the proof.

Worked Examples

Reducing a Huge Power

Modular Inverse via FLT

Common Misconceptions

The Converse Is False

The implication runs prime ⟹ congruence, not the reverse. From "$a^{n-1}\equiv 1(\mathrm{mod}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.

Carmichael Number 561

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

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.

Connections

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(\mathrm{mod}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(\frac{a}{p}\right)$.

Real-World Applications

1. RSA cryptosystem (Rivest–Shamir–Adleman, 1977). Decryption correctness $m^{ed}\equiv m(\mathrm{mod}n)$ follows directly from FLT/Euler's theorem applied to $n=pq$, with $ed\equiv 1(\mathrm{mod}\phi (n))$.
2. Fermat primality test. A fast probabilistic check: if $a^{n-1}\not\equiv 1(\mathrm{mod}n)$ for some $a$, then $n$ is definitely composite.
3. Miller–Rabin primality test. The strong refinement that powers modern cryptographic key generation (e.g., OpenSSL, GnuPG) rests on Fermat-type congruences plus square-root structure.
4. Modular exponentiation and inverses. Computing $a^{-1}\equiv a^{p-2}$ (as in Example 2) is used in elliptic-curve and finite-field arithmetic, including ECDSA signatures.
5. Pseudorandom number generators. Lehmer/multiplicative congruential generators choose multipliers that are primitive roots, whose maximal period $p-1$ is governed by FLT and equation [3].
6. Error-correcting codes. Reed–Solomon and BCH codes operate over finite fields ${\mathbb{F}}_p$ and ${\mathbb{F}}_{p^k}$, where every nonzero element satisfies $x^{p^k-1}=1$, the field analogue of FLT.
7. Hashing and checksums. Rolling polynomial hashes modulo a prime exploit FLT to invert and roll the hash window in $O(1)$.

Historical Development

• 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 $\phi (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.

Subtleties & Limits

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}\mathrm{mod}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.

See Also