Fermat's little theorem

Raising numbers to high powers usually makes them explode in size. But if you only care about the remainder after dividing by a prime, a surprising regularity appears: the powers settle into a predictable pattern that always loops back. Fermat's little theorem pins down that pattern exactly.

The theorem: if p is a prime and a is any integer, then a^p ≡ a (mod p). When a is not divisible by p, you may divide through by a to get the often-quoted form a^(p−1) ≡ 1 (mod p). For example with p = 5 and a = 2: 2^4 = 16 = 15 + 1, and 16 ≡ 1 (mod 5).

This is a workhorse of computation and a building block of cryptography, since it lets you collapse enormous exponents modulo a prime. Two honest cautions. First, the clean a^(p−1) ≡ 1 form needs a not divisible by p; if p divides a, both sides are simply 0. Second, the converse fails: a number n passing a^(n−1) ≡ 1 (mod n) is not guaranteed prime — composite Carmichael numbers fool the test — so it gives strong evidence, not proof, of primality.