Fermat's Little Theorem (Visualization)

Bob makes multicolored bead earrings and discovers that forming strings into rings creates unexpected equivalences—six distinct strings collapse into only two distinguishable necklaces.

The necklace visualization exemplifies combinatorial proof—establishing algebraic results through counting arguments rather than algebraic manipulation.

Fermat’s Little Theorem underlies modern public-key cryptography—particularly RSA encryption—enabling secure internet communication, digital signatures, and cryptocurrency.

Understanding necklace counting requires recognizing that cyclic rotations group multiple distinct strings into single equivalence classes.

Fermat stated his “little theorem” in 1640 without proof; Euler provided the first published proof nearly a century later in 1736, validating Fermat’s insight and extending it.

Pierre de Fermat stated his “little” theorem in 1640: for any integer a and prime p, a^p ≡ a (mod p), or equivalently (if a not divisible by p), a^(p-1) ≡ 1 (mod p).

Fermat’s Little Theorem follows from Lagrange’s theorem in group theory applied to the multiplicative group of integers modulo prime p.

Fermat’s Little Theorem enables efficient modular exponentiation—computing a^k mod p for enormous k without calculating a^k directly.

Fermat’s Little Theorem provides a probabilistic primality test: if a^(n-1) ≢ 1 (mod n) for some a, then n is definitely composite; if a^(n-1) ≡ 1 (mod n), n is probably prime.

When necklace size is prime, multicolored strings partition into equivalence classes of uniform size—each containing exactly p strings (where p is the prime).