Fermat's Little Theorem

Overview

Fermat's little theorem is a universal statement about powers modulo a prime. It lets one reduce large exponents and detect some composite numbers without factoring them. Its strength comes from working in a finite multiplicative group. The hypotheses are indispensable, and the converse is false: passing a particular power test does not establish primality.

Prerequisites

Understand congruence, prime numbers and coprimality. A nonzero residue modulo a prime is invertible. For the group interpretation, know the order of an element and Lagrange's theorem; the elementary proof only requires cancellation of invertible residues.

Definition and conventions

If $p$ is prime and $a$ is an integer with $p\nmid a$, then

An equivalent formulation, with no restriction on $a$, is $a^p\equiv a\pmod p$. For multiples of $p$, this second statement holds because both sides are zero modulo $p$. For other integers, multiply the first statement by $a$. This is the little theorem, not Fermat's last theorem about sums of positive integer powers.

Intuition

Multiplication by a nonzero residue rearranges the nonzero residues modulo $p$. It cannot lose a residue, create a zero, or identify two different residues because multiplication is invertible. The theorem captures a numerical consequence of this finite symmetry. It does not say that $p-1$ is the smallest exponent giving one.

Examples and non-examples

To find $2^{100}$ modulo $13$, use $2^{12}\equiv1$. Since $100=8\cdot12+4$, the answer is $2^4\equiv3\pmod{13}$. This reduces a large calculation to one small power.

For the composite modulus $9$, $2^8\equiv4$, not one. Yet some composite moduli pass particular tests: $341=11\cdot31$ and $2^{10}=1024\equiv1\pmod{341}$, so $2^{340}\equiv1\pmod{341}$. This explicit counterexample prevents reversing the theorem even for an integer coprime to the modulus.

Important properties

An elementary proof compares the product of all nonzero residues with its image after multiplication by $a$. The image is a permutation, so the products agree. Factoring out one $a$ from each of the $p-1$ terms gives $a^{p-1}$ times the original product. The product is invertible, so cancellation gives the theorem.

Equivalently, the group $(\mathbb Z/p\mathbb Z)^\times$ has $p-1$ elements. The order of $[a]$ divides $p-1$ by Lagrange's theorem. Thus a failed congruence proves compositeness, but a successful congruence may reflect only one element's order, not the primality of the modulus.

Connections and further reading

Euler's theorem replaces $p-1$ with the number of units for a composite modulus and explicitly requires coprimality. More sophisticated primality tests use stronger conditions. Conrad's note treats the elementary proof and testing limitations.