Concept

Primitive root

A number whose powers, taken modulo a prime, run through every non-zero remainder before repeating. Every prime has one, and choosing one turns multiplication of remainders into addition of exponents, the way logarithms do for real numbers.

Named by 5 essays across 4 fields — each of them below, with the objects they name alongside it.

A witness that 97 is prime: 5 has order 96. A table of the checks Lucas's test makes on 97 with base 5: the power (n − 1)/q for each prime q dividing n − 1, none of which is 1.

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.

number · Fermats little theorem

The 3 periods of the 13th roots of unity, and the equation they solve. Roots of unity modulo 13 grouped by the cosets of the index-3 subgroup; the periods 0.274, 1.377, −2.651 are the roots of x³ + x² − 4x + 1.

The sums that obey a smaller equation

The twelve non-trivial thirteenth roots of unity satisfy an equation of degree twelve. Split them into three groups of four — the right three groups — and add each group: the three sums are the roots of x³ + x² − 4x + 1, an equation of degree three with whole-number coefficients. Gauss called such sums periods, found one for every divisor of p − 1, and used them to build the seventeen-gon from four quadratic equations.

algebra · Roots of unity

How long x² + c runs before repeating, for four constants. Four survival staircases on a logarithmic scale of length: two following the birthday curve, and two for c equal to 0 and minus 2 lying far to the right.

Two constants that do not walk at random

Pollard's factoring method trusts x² + c modulo a prime to repeat as soon as a random function would, after about √p steps. For c = 1 and c = 3 it does. For c = 0 and c = −2 it runs twelve to eighteen times longer on average, with almost no tail and enormous cycles, because those two maps are multiplication in disguise and their cycles are set by the order of 2 rather than by chance. Every other constant walks at random — including in the one respect in which x² + c is plainly not random, that it is two-to-one.

probability · Birthday problem

Dots that never repeat a step

Place n dots on an n-by-n grid, one in each row and column, so that no two pairs of dots are joined by the same step. These Costas arrays were invented for sonar, and finite fields build them: a primitive root modulo a prime gives one family, a pair of primitive elements in any finite field another. Yet the constructions account for almost none of the arrays that exist — 92 of the 2,160 of order ten — and for orders 32 and 33 nobody has found a single one.

computation · Finite fields

Forty-two squares in a row. p = 366791: partial sums of (n/p) for n ≤ 200: 0, 10, 20, 30, 40, 46, 54, 60, 64, 72, 78, 78, 88, 92, 98, 102, 108, 116, 122, 126, 132; least non-residue 43.

The first number that is not a square

Modulo a prime, half the numbers are perfect squares. Count up from 1 and the first non-square is usually 2 or 3 — but modulo 366,791 the numbers 1 to 42 are all squares. How far the run of squares can last is one of the oldest open questions about primes: the truth is tiny, the proofs are huge, and the Riemann hypothesis would close most of the gap.

number · Quadratic reciprocity

Named alongside it

The objects these essays reach for when they reach for this one.

Birthday problem Carmichael number Chebyshev polynomial Collision Conjecture Constructible number Coset Cyclotomic polynomial Exhaustive search Fermats little theorem Field extension Finite field

All concepts