Foundations — Fermat's little theorem (statement)

Before you can believe the theorem, you must be able to read it. Every symbol below is built in an order where each one only uses ideas already defined.

1. Counting numbers and division-with-remainder

Everything starts with the whole numbers $0,1,2,3,\dots$ and one very old idea: sharing into equal groups leaves a leftover.

Look at the figure: $17$ pebbles in rows of $5$ give $3$ full rows ($q=3$) and $2$ left over ($r=2$), matching $17=3\cdot 5+2$. The remainder is the only part we will care about from here on.

2. The symbol $\mathrm{mod}$ — "just the remainder"

Why does the topic need this? Fermat's theorem is entirely a statement about remainders. We never care that $81$ is big; we care only that $81\mathrm{mod}5=1$. The symbol $\mathrm{mod}$ throws away the bulky quotient and keeps the one digit that matters.

3. The clock picture and the symbol $\equiv$ (congruence)

Here is the single most important picture in all of modular arithmetic.

Why the topic needs it: the theorem's conclusion $a^{p-1}\equiv 1(\mathrm{mod}p)$ is a congruence, not an equation. It says the giant number $a^{p-1}$ lands on the "$1$" mark of the $p$-hour clock.

See Modular Arithmetic Basics for the full arithmetic (adding and multiplying on the clock).

4. The divides symbols $\mid$ and $\nmid$

The theorem's condition $p\nmid a$ means "$a$ is not a multiple of $p$", which on the clock means "$a$ does not sit on the $0$ mark". That non-zero starting position is exactly what makes the magic possible — a starting hand parked at $0$ would just stay at $0$ forever.

5. Prime numbers

Look at the figure: $12$ pebbles can form a neat $3\times 4$ rectangle — it factors, so it is composite. $11$ pebbles refuse every rectangle except the flat $1\times 11$ line — that stubbornness is primality.

Why the topic needs primes specifically: on a $p$-hour clock with $p$ prime, multiplying by any non-zero number shuffles the marks $\{1,2,\dots ,p-1\}$ without ever collapsing two of them together. On a composite clock (like $4$ hours) that shuffle breaks — which is exactly why the parent's $2^3\equiv 0(\mathrm{mod}4)$ counterexample fails the theorem. More at Properties of Prime Numbers.

6. The greatest common divisor $\gcd$ and "coprime"

For a prime $p$, saying $\gcd (a,p)=1$ is the same as saying $p\nmid a$ — because the only divisors of $p$ are $1$ and $p$, so the only way to share a factor with $p$ is to be a multiple of $p$. That is why the parent lists them as equivalent conditions.

7. Powers $a^n$

Why the topic needs it: the theorem is about repeated multiplication on the clock. Fermat's claim is that after exactly $(p-1)$ such multiplications, the hour hand returns to the $1$ mark.

8. The factorial $(p-1)!$

The intuitive proof-sketch in the parent uses one more symbol.

Why the topic needs it: the "multiply every element on both sides" trick collects the numbers $1,2,\dots ,p-1$ into one product, and that product is $(p-1)!$. Because $p$ is prime, none of $1,\dots ,p-1$ share a factor with $p$, so $(p-1)!$ is coprime to $p$ and can be cancelled — leaving $a^{p-1}\equiv 1$. (Its own remainder mod $p$ is the subject of Wilson's Theorem.)

How these foundations feed the theorem

Read top to bottom: division-with-remainder is the seed; from it grow $\mathrm{mod}$, congruence, and the divides relation; primes and coprimality branch off; powers and the factorial are the machinery; all of them converge on the theorem statement.

Where this leads next

• Multiplicative Group Modulo Prime — the shuffle of $\{1,\dots ,p-1\}$ under multiplication, made rigorous.
• Euler's Totient Function — what replaces $(p-1)$ when the clock is composite.
• Modular Exponentiation Algorithms — how to compute $a^{p-1}$ without ever writing the giant number.
• Carmichael Numbers — composites that fake the theorem for every base.
• RSA Cryptosystem — the payoff that made this theorem famous.

Equipment checklist

Cover the right side and see if you can state each from memory.