What is Fermat's Little Theorem, and what are its conditions and corollaries?

If p is prime and $\gcd(a, p) = 1$, then $a^{p-1} \equiv 1 \mod p$. This provides a shortcut for modular exponentiation and computing inverses.

The theorem: For prime $p$ and $\gcd(a, p) = 1$: $$a^{p-1} \equiv 1 \mod p$$

Equivalent forms:

• $a^p \equiv a \mod p$ (multiplying both sides by $a$)
• $a^{p-2} \equiv a^{-1} \mod p$ (dividing both sides by $a$ — gives the inverse!)

Example: $a = 4$, $p = 5$:

• $4^{5-1} = 4^4 = 256 \equiv 1 \mod 5$ ✓
• $4^5 = 1024 \equiv 4 \mod 5$ ✓
• $4^{5-2} = 4^3 = 64 \equiv 4 \mod 5$, and indeed $4 \cdot 4 = 16 \equiv 1 \mod 5$ ✓

Critical conditions:

• $p$ must be prime — if $p = 9$ (not prime) and $a = 7$: $7^{9-1} = 7^8 \equiv 4 \not\equiv 1 \mod 9$
• $\gcd(a, p) = 1$ — if $a = 14$, $p = 7$: $\gcd(14, 7) = 7 \neq 1$, so $14^6 \equiv 0 \not\equiv 1 \mod 7$

Cryptographic use: Fermat's theorem lets you compute $a^{-1} \mod p$ without the Extended Euclidean Algorithm — just compute $a^{p-2} \mod p$ using SAM.

Go deeper:

• Fermat's little theorem (Wikipedia) — statement, proof and its role in primality testing.
• Satz von Euler (-Fermat) — worked examples (German) — step-by-step numeric practice with the theorem.