Concept

Quadratic residue

A number that is the square of something else in modular arithmetic. Exactly half the non-zero residues modulo an odd prime are squares, and joining two points when their difference is one gives colourings with unusually few large single-coloured sets.

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

Counting a 5 by 3 rectangle two ways. Lattice points in a rectangle cut by a diagonal of slope q over p, coloured by which side they fall.

Counting one rectangle, twice

Whether seven is a square modulo eleven, and whether eleven is a square modulo seven, are two unrelated-looking questions. Their answers are linked, and the link is a rectangle of dots counted along its rows and then along its columns.

number · Quadratic reciprocity

17 points coloured by whether their difference is a square. 17 points on a circle with every pair joined, coloured by whether the difference of their labels is a square modulo 17; the largest set of points all joined by one colour has 3 members.

Eighteen people, and the seventeen that escape

Among any eighteen people, four are mutual acquaintances or four are mutual strangers. Seventeen can be arranged so that neither happens, and the arrangement is not a lucky find — it is a rule about squares.

discrete · Ramsey theory

The two supplements, and the residue classes that decide them. A table of odd primes with the Legendre symbols of minus one and two beside the residue of p modulo four and modulo eight.

The two supplements, and where the eight comes from

The main law relates two odd primes to each other and says nothing about −1 or about 2. Those two are settled separately, by their own counts, and the answers arrive modulo four and modulo eight — which is a clue about where the whole subject is really taking place.

number · Quadratic reciprocity

Multiplication by 3 modulo 11, and the sign of the shuffle. Residues in two rows joined by strings showing where multiplication sends each one, with a strip beneath comparing the sign of the shuffle to the Legendre symbol for every multiplier.

The symbol is the sign of a shuffle

Multiplying every residue modulo p by a fixed number rearranges them. That rearrangement is a permutation, permutations have a sign, and the sign is exactly the Legendre symbol — so a question about squares becomes a question about crossings.

number · Quadratic reciprocity

The Gauss sum for 13, added one root at a time. Partial sums of the p-th roots of unity signed by the Legendre symbol, drawn as a walk closing on a point at distance root p from the origin.

One sum, squared two ways

Add the p-th roots of unity, each taken with a plus or a minus according to whether its index is a square. The walk that results closes on a point at distance √p from the origin — and squaring that one number, evaluated two different ways, is the reciprocity law.

number · Quadratic reciprocity

Where a congruence decides which primes a form represents, and where it does not. Rows of primes marked by whether each is represented by x squared plus n y squared, with the residue classes that decide it where such classes exist.

Which primes a form takes

A prime is the sum of two squares exactly when it is 1 modulo 4. Change the form slightly, to x² + 27y², and no congruence on p decides it at all — which is where the elementary subject ends and its successor begins.

number · Quadratic reciprocity

Randomness that has to be earned

A generator that resists prediction cannot be built out of a rule anybody can fit. It has to be built out of a computation believed hard to undo, and the belief is the load-bearing part — which makes cryptographic randomness a conditional statement rather than a construction.

computation · Pseudorandomness

The primes below 100,000, by remainder mod 4. A bar for each remainder on division by 4, showing how many primes below 100000 leave it. The 2 classes sharing no factor with 4 hold near-equal counts; the rest are empty or hold one prime.

Infinitely many of one kind

Euclid's argument produces a prime nobody had listed, and says nothing about what it looks like. Ask for infinitely many primes ending in 3, or leaving a remainder of 1 on division by 4, and the same construction has to be aimed — and for most targets nobody knows how to aim it.

number · Infinitude of primes

Named alongside it

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

Modular arithmetic Legendre symbol Quadratic reciprocity Counting two ways Primes Gauss lemma Gaussian integers Parity Primitive element Sums of two squares Unique factorisation Complete graph

All concepts