Fermat's Little Theorem

a^p-1 1 p for prime p — modular arithmetic's most useful identity.

The idea

Theorem (Fermat's little theorem).

Let $p$ be a prime and let $a$ be an integer that $p$ does not divide. Then $a^{p-1} \equiv 1 \pmod{p}.$ Equivalently, $a^{p} \equiv a \pmod{p}$ for every integer $a$.

Some repetition among the powers of $a$ is expected: there are only finitely many residues modulo $p$, so the sequence $a, a^{2}, a^{3}, \ldots$ must eventually repeat and settle into a cycle. The theorem says more: the exponent $p - 1$ always returns the power to $1$, whichever $a$ we start from, so the cycle length divides $p - 1$.

The theorem's main use is reducing exponents. Since $a^{p-1} \equiv 1$, multiplying by a factor of $a^{p-1}$ changes nothing modulo $p$, so $a^{k}$ modulo $p$ depends only on $k$ modulo $p - 1$. An exponent in the hundreds or the billions reduces to one below $p - 1$ before any multiplication is done.

Ways to work on it

• Walkthrough. Verify the theorem for a small prime, one multiplication at a time.
• Proof. See why it's true — a visual counting proof with bead necklaces.
• Practice. Verify Fermat's Little Theorem for random small primes.
• Hardest. Use Fermat's Little Theorem to reduce a huge exponent mod p.

Not sure where to start? Take the ten-question placement test.