Fermat's little theorem (statement): Visual walkthrough

Before anything else, let us agree on the picture we will draw on the entire page.

We will prove: if you pick a number $a$ that does not land on tick $0$ (i.e. $p ∤ a$ , read " $p$ does not divide $a$ "), then $a^{p - 1}$ lands on tick $1$ .

Step 1 — The tick marks we care about

WHAT. Throw away tick $0$ . Keep only the non-zero ticks: $call this set S {1, 2, 3, \dots, p - 1}$ Here $S$ is just a name for this collection of $p - 1$ ticks. Nothing more.

WHY. Tick $0$ is special: any number that lands there stays stuck there under multiplication ( $0 \times a = 0$ ). It cannot participate in the "everything gets 1" magic, so we set it aside. That is exactly the coprimality condition doing its job in advance.

PICTURE. The clock below has $p = 7$ . The green ticks are $S = {1, 2, 3, 4, 5, 6}$ ; the red tick is $0$ , quarantined.

Figure — Fermat's little theorem (statement)

Step 2 — Multiplying the whole clock by $a$

WHAT. Pick our number $a$ (with $p ∤ a$ ). Take every tick in $S$ and multiply it by $a$ , then land it back on the clock: $a \cdot 1, a \cdot 2, a \cdot 3, \dots, a \cdot (p - 1) (mod p)$ Each term $a \cdot k$ says "start at tick $k$ , then jump to tick number $a$ times $k$ , wrapping around."

WHY. We want to compare "the ticks before multiplying" with "the ticks after multiplying." That comparison is the entire engine of the proof, so first we have to see what multiplication by $a$ does to the clock.

PICTURE. Below, $p = 7$ and $a = 3$ . Each green arrow sends tick $k$ to tick $3 k mod 7$ . Notice the arrows land on $3, 6, 2, 5, 1, 4$ — scrambled, but every arrowhead is on a different non-zero tick.

Step 3 — The key claim: no collisions, no zeros

WHAT. The outputs $a \cdot 1, a \cdot 2, \dots, a \cdot (p - 1)$ are:

never tick $0$ , and
all different from one another.

WHY (this is the heart — and where "prime" is essential).

No zeros. Suppose $a \cdot k$ landed on $0$ , meaning $p ∣ a \cdot k$ . Since $p$ is prime, if $p$ divides a product it must divide one of the factors (Properties of Prime Numbers). But $p ∤ a$ (our choice) and $p ∤ k$ (because $k$ is between $1$ and $p - 1$ ). Contradiction. So no output is $0$ .

No collisions. Suppose two inputs collided: $a \cdot k \equiv a \cdot j (mod p)$ . Then $a \cdot (k - j) \equiv 0$ , so $p ∣ a (k - j)$ . Again by primality $p ∣ a$ or $p ∣ (k - j)$ . First is false; and $k - j$ is between $- (p - 2)$ and $p - 2$ , so the only way $p ∣ (k - j)$ is $k = j$ . Two "different" inputs were secretly the same. So no genuine collisions.

PICTURE. $p - 1$ arrows, each pointing at a distinct non-zero tick. With $p - 1$ arrows and exactly $p - 1$ non-zero ticks and no repeats, every non-zero tick is hit exactly once. The outputs are the set $S$ reshuffled.

Step 4 — Same ticks in, same ticks out ⇒ same product

WHAT. Because the outputs are just $S$ shuffled, the product of all outputs equals the product of all inputs: $product of the shuffled ticks (a \cdot 1) (a \cdot 2) \dots (a \cdot (p - 1)) \equiv product of the original ticks 1 \cdot 2 \dots (p - 1) (mod p)$

WHY. Multiplication doesn't care about order: $3 \times 5 = 5 \times 3$ . If two bags hold the same numbers (just poured in a different order), multiplying each bag gives the same total. Step 3 guaranteed the two bags hold exactly the same ticks.

PICTURE. Two bags side by side. Left bag: the original ticks $1, 2, \dots, p - 1$ . Right bag: the same ticks, colour-shuffled. A big " $=$ " between their products.

Step 5 — Pull the $a$ 's out

WHAT. On the left side there are $p - 1$ copies of $a$ , one from each factor. Collect them: $the p - 1 collected a ’s a^{p - 1} \cdot the leftover ticks (1 \cdot 2 \dots (p - 1)) \equiv same leftover ticks (1 \cdot 2 \dots (p - 1)) (mod p)$

WHY. The exponent $p - 1$ is not chosen by magic — it is simply how many non-zero ticks there are. Every one of the $p - 1$ factors on the left carried exactly one $a$ ; gathering them turns $a \cdot a \dots a$ into the shorthand $a^{p - 1}$ .

PICTURE. The left product visually "unzipping" into $a^{p - 1}$ times the tick-product, with each $a$ lifted out of its factor.

Let us give the leftover a name: $(p - 1)! = 1 \cdot 2 \dots (p - 1)$ (the "factorial" — just the product of all non-zero ticks). It appears identically on both sides. So: $a^{p - 1} \cdot (p - 1)! \equiv (p - 1)! (mod p)$

Step 6 — Cancel the leftover safely

WHAT. Both sides carry the factor $(p - 1)!$ . Remove it: $a^{p - 1} \equiv 1 (mod p)$

WHY (why cancelling is legal here). You may only cancel a factor modulo $p$ if that factor is itself invertible — i.e. coprime to $p$ . Is $(p - 1)!$ coprime to $p$ ? Yes: it is a product of the numbers $1, \dots, p - 1$ , and none of them shares a factor with the prime $p$ . So it never lands on tick $0$ and can be cancelled. (This same "cancelling is safe" fact is why Wilson's Theorem is even able to pin $(p - 1)!$ down to $- 1$ .)

PICTURE. The identical $(p - 1)!$ factor lifting off both sides of the balance scale, leaving $a^{p - 1}$ on the left and $1$ on the right — and the scale still balanced.

Step 7 — The degenerate case: what if $a$ is a multiple of $p$ ?

WHAT. Suppose $p ∣ a$ , so $a$ lands on tick $0$ . Then $a^{p - 1}$ also lands on $0$ , not $1$ — the classical form genuinely fails. But the alternative form still holds: $a^{p} \equiv a (mod p) for e v er y integer a .$

WHY. Two cases exhaust everything:

If $p ∤ a$ : multiply Step 6 by $a$ once more — $a^{p} = a \cdot a^{p - 1} \equiv a \cdot 1 = a$ .
If $p ∣ a$ : then $a \equiv 0$ and $a^{p} \equiv 0$ , so both sides are tick $0$ ; still equal.

Either way $a^{p} \equiv a$ . Nothing is left uncovered.

PICTURE. Two mini-clocks: left ( $a = 3$ , $p = 7$ ) shows $a^{p - 1}$ hitting tick $1$ ; right ( $a = 7$ , $p = 7$ ) shows $a$ stuck on tick $0$ — the alternative form catching the case the classical form drops.

The one-picture summary

The whole derivation on one canvas: multiply the clock by $a$ ⇒ ticks reshuffle (prime = no collisions) ⇒ same bag ⇒ same product ⇒ pull out $p - 1$ copies of $a$ ⇒ cancel the common $(p - 1)!$ ⇒ land on $1$ .

Recall Feynman retelling (say it in plain words)

I have a clock with a prime number of ticks and I ignore the zero tick. I pick a number $a$ that isn't zero on the clock. I multiply every remaining tick by $a$ . Because the number of ticks is prime, no two ticks ever crash into each other and none falls onto zero — so I get back exactly the same ticks, just shuffled. Since the same numbers came out (in a new order), multiplying them all gives the same total as before. But every factor on the "after" side smuggled in one copy of $a$ , and there were $p - 1$ factors, so the after-total is really $a^{p - 1}$ times the before-total. Same total on both sides means the extra $a^{p - 1}$ must equal $1$ . And if $a$ was zero on the clock all along, I just note that $a^{p}$ and $a$ are both zero — so the " $a^{p} \equiv a$ " version never fails.

Recall

Why can we cancel $(p - 1)!$ modulo a prime $p$ ? ::: Because $(p - 1)!$ is a product of numbers all coprime to $p$ , so it is itself coprime to $p$ and therefore invertible — you can divide by it. In Step 3, exactly which fact about primes forbids collisions? ::: If a prime divides a product $a (k - j)$ , it must divide one of the factors; since $p ∤ a$ and $∣ k - j ∣ < p$ , we're forced to $k = j$ . Where does the exponent $p - 1$ actually come from? ::: It is the count of non-zero ticks; each of the $p - 1$ factors contributes one $a$ .

Connections

Fermat's little theorem (statement) — the parent statement this page derives.
Modular Arithmetic Basics — the clock and $\equiv (mod p)$ .
Properties of Prime Numbers — " $p ∣ ab \Rightarrow p ∣ a$ or $p ∣ b$ ", used in Step 3.
Multiplicative Group Modulo Prime — the shuffle is bijectivity of $(Z / p Z)^{*}$ .
Wilson's Theorem — pins down the very $(p - 1)!$ we cancelled.
Euler's Totient Function — replaces $p - 1$ by $ϕ (n)$ for composite moduli.
Carmichael Numbers — composites that fake the "no collisions" picture.
Modular Exponentiation Algorithms — using the result to compute fast.
RSA Cryptosystem — the payoff application.