Matpic
mathematics, in pictures
Concept

Euclidean algorithm

Repeatedly replacing a pair of numbers by the smaller and the remainder, until nothing is left over. It finds the greatest common divisor, and a ring in which it can be run has unique factorisation as a consequence.

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

φ as a continued fraction. The nested fraction, one quotient per step, descending to the right.

A fraction that never closes

Euclid's algorithm throws away everything except the number of squares it peeled at each step. Those counts are a second name for the number it started from — one that terminates exactly when the ratio is a ratio.

number · Euclidean algorithm The twenty-four unit quaternions, at the corners of a four-dimensional solid. The twenty-four units of the Hurwitz quaternions drawn as the vertices of a 24-cell projected into three-space, with the ninety-six edges joining units at distance one.

The integers among the quaternions

The obvious integer quaternions are the ones with whole coordinates, and they are the wrong ones. Sixteen more, with every coordinate a half, have to be let in — and with them comes a division algorithm, twenty-four units instead of eight, and a regular solid that exists only in four dimensions.

algebra · Quaternions The two squares of 97, produced by division. A table of the division chain on 97 and a square root of minus one modulo it, with each row's quotient and remainder, the point at which the remainder falls below the square root marked, and the two squares that add to 97.

The two squares actually produced

Three proofs say a prime one more than a multiple of four is a sum of two squares, and not one of them hands over the squares. Running the Euclidean algorithm half-way does — and where to stop is the whole of the correctness argument.

number · Sums of two squares Where discs of radius one cover the lattice, and where they leave holes. Six lattices of algebraic integers drawn as points in the plane with a unit disc around each; for five of them the discs cover the whole plane and for the sixth, the integers of the field of the square root of minus nineteen, uncovered holes remain.

Factoring uniquely with no way to divide

Unique factorisation is proved by dividing with a small remainder, and in the Gaussian integers that works because discs of radius one cover the plane. In the integers of ℚ(√−19) the discs leave holes, no division algorithm of any kind can be made to work — and factorisation is unique anyway. The same field is why n² + n + 41 is prime forty times running.

number · Unique factorisation Euclid's game on 34 and 21. A 34 by 21 rectangle tiled by the squares of Euclid's algorithm, each run of equal squares shaded by the player who faces it, with the deciding run outlined.

The player who meets the first long run

Turn Euclid's algorithm into a game: two players take turns cutting squares off the rectangle, any number from the current run, and whoever cuts the last one wins. The whole game is decided before it starts — by whether the ratio of the sides is more or less than the golden ratio, which is the same thing as how many runs of length one come first.

geometry · Euclidean algorithm Counting the real roots of x⁵ − 5x³ + x² + 3x − 1 with Euclid's algorithm. Above, the graph of a polynomial over an interval with its real roots marked; below, a step function counting sign changes in the polynomial's Sturm chain, which drops by one at each root; beside them the chain of polynomials listed.

The remainders that count the roots

Run Euclid's algorithm on a polynomial and its derivative, flipping the sign of each remainder, and write down the signs of the whole chain at any point. The number of sign changes drops by exactly one each time the point passes a real root — so the roots in any interval can be counted, exactly, without finding a single one.

geometry · Euclidean algorithm A twist along the horizontal loop, done once. Squares with opposite edges glued and a shaded horizontal band, showing one loop before and after the torus is twisted along the band.

A twist that carries one loop to another

Cut a torus along a loop, turn one side of the cut once round, and glue it back. Nothing is torn, so every loop that did not cross itself still does not — but a loop of class (0, 1) is now a loop of class (1, 1). Two such twists reach every loop that never crosses itself, by Euclid's algorithm, and the symmetries they generate are exactly the whole-number matrices of determinant one.

topology · Homotopy A 33 × 32 rectangle cut into 9 unequal squares. A squared rectangle of 9 squares with sides 18, 15, 14, 10, 9, 8, 7, 4, 1, each labelled with its size.

A rectangle made only of squares

A rectangle can be cut into finitely many squares — of any sizes, as many as wanted — exactly when its two sides are in whole-number proportion. Max Dehn proved it in 1903, and the proof that stuck, found by four Cambridge undergraduates in 1940, reads the squares as currents in an electrical circuit.

computation · Scissors congruence

Named alongside it

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

LatticeNormContinued fractionsFibonacciGaussian integersGreatest common divisorGolden ratioInvariantUnique factorisationAlgebraic integerBackward inductionContinued fraction convergent

All concepts