Primality test
Named by 7 essays across 2 fields — each of them below, with the objects they name alongside it.
Necklaces that prove a theorem
Thread five beads in two colours, thirty-two ways. Two of them are all one colour; the other thirty fall into rings of five. That count, and nothing else, is Fermat's little theorem.
The exponent that is smaller than Euler's
Euler's theorem raises every unit to the count of the units and gets one. The smallest exponent that works for all of them at once is often much smaller — and a composite is invisible to Fermat's test exactly when that smaller number divides n − 1.
Every power sum, from the coefficients alone
Raise the roots of a polynomial to the k-th power and add them. However the roots turn, the total is a whole number when the coefficients are, and Newton's identities produce it from the coefficients one step at a time — no root is ever found. Run the rule on x³ − x − 1 and out comes Perrin's sequence, whose terms know which numbers are prime, nearly.
An order that proves a prime
Fermat's little theorem is a test that primes pass and composites mostly fail, and it can be fooled. Run backwards, it cannot. If some number a has order exactly n − 1 modulo n, then n is prime — because only a prime has n − 1 numbers to cycle through. Checking that takes the prime factors of n − 1, which need proofs of their own, and the proofs nest into a tree that anyone can check: Pratt's certificate, which shows every prime has a short proof of being one.
The row that proves a prime
Fermat's little theorem can be fooled: 561 passes it for every base and is not prime. Thread necklaces with a fixed number of black beads instead of any colours at all, and the count becomes a statement about a whole row of Pascal's triangle — every middle entry of row n is a multiple of n exactly when n is prime — which no composite can fake. Written as polynomials it is (x + a)ⁿ = xⁿ + a, and cut down to size it is the first proof that primes can be recognised in polynomial time.
Euler's sixty-five convenient numbers
For some n, whether a prime can be written as x² + ny² is settled by its remainder on division by 4n alone, the way a prime's remainder on division by four settles whether it is a sum of two squares. Euler found sixty-five such n, from 1 to 1,848, called them convenient, and used the largest to prove that 18,518,809 is prime. Every one of them is a number whose class group has no element of order more than two — and whether the list is complete is still not known.
Euclid's proof run as a machine
Euclid proved there is no last prime by multiplying the primes on any list, adding one, and noting that the result has a prime factor not on the list. Run the proof as a machine — start from 2, and each time take the smallest prime factor of one more than the product so far — and it produces 2, 3, 7, 43, 13, 53, 5, 6221671, … a sequence that never repeats, that reaches small primes late and large ones early, and that nobody can prove reaches every prime.
Named alongside it
The objects these essays reach for when they reach for this one.
Fermats little theoremModular arithmeticPrimesCompositeCounting two waysExhaustive searchOrderPolynomialBinomial coefficientCarmichael numberClass groupClass number