Fermat's Little Theorem — Pick a Prime, Pick a Base, Watch a^(p−1) Collapse to 1

Fermat's little theorem is one of the cleanest identities in all of mathematics. Pick any prime p. Pick any integer a that is not a multiple of p. Raise a to the power p - 1, take the result modulo p, and the answer is always 1.

a^{p-1} \equiv 1 \pmod p \qquad \text{(when } p \text{ prime and } \gcd(a, p) = 1\text{)}

No matter what p is. No matter what a is. The collapse to 1 is guaranteed. This visualisation lets you drag p through the first few primes and a through small bases, and verify the theorem by direct computation each time. The pattern is striking — and once you see it, the proof is inevitable.

Drag p and a, watch the collapse

prime p: base a = 3:

Pick a prime $p$ from the dropdown and slide the base $a$. The canvas computes the full sequence $a^1, a^2, \dots, a^{p-1}$ modulo $p$ and highlights the final entry. Whenever $\gcd(a, p) = 1$, the last column reads exactly $1$ — Fermat's little theorem confirmed. Try $p = 7$ with $a = 3$: $3^6 = 729 = 7 \times 104 + 1 \equiv 1 \pmod 7$. Try $p = 11$ with $a = 2$: $2^{10} = 1024 = 11 \times 93 + 1 \equiv 1 \pmod{11}$. The pattern is relentless.

Hand-verify a few cases

Here are the full power sequences mod p for small primes and bases. The last column is a^{p-1} \bmod p, which Fermat predicts is always 1.

p	a	a^1, a^2, a^3, \dots, a^{p-1} \pmod p	a^{p-1} \pmod p
5	2	2, 4, 3, 1	1 ✓
5	3	3, 4, 2, 1	1 ✓
7	2	2, 4, 1, 2, 4, 1	1 ✓
7	3	3, 2, 6, 4, 5, 1	1 ✓
7	5	5, 4, 6, 2, 3, 1	1 ✓
11	2	2, 4, 8, 5, 10, 9, 7, 3, 6, 1	1 ✓
11	3	3, 9, 5, 4, 1, 3, 9, 5, 4, 1	1 ✓
13	2	2, 4, 8, 3, 6, 12, 11, 9, 5, 10, 7, 1	1 ✓

Three patterns jump out:

The final entry is always 1. Without exception, as long as a is not a multiple of p.
The cycle length divides p - 1. For p = 7, a = 2 the cycle length is 3 (which divides 6 = p - 1). For p = 11, a = 3 the cycle length is 5 (which divides 10 = p - 1). Even when the cycle is shorter than p - 1, it divides it.
Many rows are full permutations of \{1, 2, \dots, p-1\}. Look at p = 7, a = 3: the sequence is 3, 2, 6, 4, 5, 1, and those are all six nonzero residues. Such an a is called a primitive root modulo p.

All three observations are consequences of Fermat's theorem plus its reformulation as a group-theory statement about the nonzero residues under multiplication.

Why a^{p-1} \equiv 1 \pmod p — the clean proof

The argument is short and elegant. Fix a prime p and a base a with \gcd(a, p) = 1. Consider the p - 1 products:

a \cdot 1, \quad a \cdot 2, \quad a \cdot 3, \quad \dots, \quad a \cdot (p-1)

taken modulo p. Two key observations:

They are distinct mod p. If a \cdot i \equiv a \cdot j \pmod p with 1 \le i, j \le p-1, then p \mid a(i - j). Since \gcd(a, p) = 1, it must be that p \mid (i - j), which forces i = j (as both are in the range 1 to p-1).
They are all nonzero mod p. Since \gcd(a, p) = 1 and \gcd(k, p) = 1 for k = 1, \dots, p-1, the product a \cdot k is coprime to p, hence nonzero mod p.

Therefore the p - 1 values \{a, 2a, 3a, \dots, (p-1)a\} are exactly a rearrangement of \{1, 2, 3, \dots, p-1\} modulo p. Multiplying both sets together gives the same product:

a \cdot 2a \cdot 3a \cdot \dots \cdot (p-1)a \equiv 1 \cdot 2 \cdot 3 \cdot \dots \cdot (p-1) \pmod p

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

Since \gcd((p-1)!, p) = 1 (no factor in (p-1)! is divisible by p), you can cancel (p-1)! from both sides:

a^{p-1} \equiv 1 \pmod p

Why the cancellation is legal: dividing both sides of a congruence is valid when the divisor is coprime to the modulus. Since p is prime and every factor of (p-1)! is in \{1, 2, \dots, p-1\}, none of them is divisible by p, so the product (p-1)! is coprime to p. The division is therefore the multiplicative inverse of (p-1)! mod p — perfectly well-defined.

Why it fails for composite moduli

The theorem is specific to primes. For a composite modulus n, you do not in general have a^{n-1} \equiv 1 \pmod n. Example: n = 6 and a = 5. Then 5^{6-1} = 5^5 = 3125, and 3125 = 520 \times 6 + 5, so 5^5 \equiv 5 \pmod 6, not 1.

The generalisation to composite moduli uses Euler's totient function \phi(n):

a^{\phi(n)} \equiv 1 \pmod n \qquad \text{whenever } \gcd(a, n) = 1

When n = p is prime, \phi(p) = p - 1, and Euler's theorem reduces to Fermat's. For n = 6 and a = 5: \phi(6) = 2, and indeed 5^2 = 25 = 4 \times 6 + 1 \equiv 1 \pmod 6. ✓

One worked example

Find $7^{102} \bmod 13$.

p = 13 is prime and \gcd(7, 13) = 1, so Fermat applies: 7^{12} \equiv 1 \pmod {13}.

Step 1. Reduce the exponent mod p - 1 = 12: 102 = 8 \times 12 + 6, so 102 \equiv 6 \pmod{12}.

Why reducing mod p-1 works: 7^{102} = (7^{12})^8 \cdot 7^6 \equiv 1^8 \cdot 7^6 = 7^6 \pmod{13}. Any multiple of 12 in the exponent collapses to 1, leaving only the residue.

Step 2. Compute 7^6 \bmod 13.

7^2 = 49 = 3 \times 13 + 10 \equiv 10 \equiv -3 \pmod {13}.

7^4 \equiv (-3)^2 = 9 \pmod{13}.

7^6 \equiv 7^4 \times 7^2 \equiv 9 \times (-3) = -27 \equiv -27 + 3 \times 13 = 12 \equiv -1 \pmod{13}.

Step 3. Convert to a positive residue: -1 \equiv 12 \pmod {13}.

So 7^{102} \equiv 12 \pmod {13}.

Without Fermat you would be computing a 86-digit number. With Fermat you reduced a four-digit exponent to a one-digit one and finished in four lines of arithmetic.

The takeaway

Fermat's little theorem is the single most useful fact about modular arithmetic for exam problems involving "find the remainder when a^n is divided by a prime p." Step 1: reduce the exponent mod p - 1. Step 2: compute the small remaining power directly. The huge exponent becomes irrelevant almost as soon as you see the prime modulus.