Matpic
mathematics, in pictures
Series

Euclidean algorithm — the series

6 essays on one idea, from the one that introduces it to the one that assumes the rest.
  1. Euclid's algorithm on a 34 by 13 rectangle. The rectangle is tiled by peeling off the largest square that fits, again and again, until nothing is left.

    The oldest algorithm, drawn as a tiling

    Euclid's method for finding a greatest common divisor is usually presented as a loop. It is also a way of tiling a rectangle with squares, and the tiling explains why it works.

    part 1 · geometry
  2. φ 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.

    part 2 · number
  3. 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.

    part 3 · geometry
  4. 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.

    part 4 · geometry
  5. The proof of Descartes' rule, one term at a time. Four stacked graphs: a four-term polynomial with three positive roots, and the three polynomials obtained by dividing out a power of x and differentiating, each with one fewer term, one fewer sign change and one fewer positive root.

    What the signs allow

    Descartes' rule reads the signs of a polynomial's coefficients and bounds its positive roots by how often they change — a bound set by the number of terms, not the degree, and proved by nothing more than Rolle's theorem. Each count the rule allows can be had. But not every pair of counts, positive and negative, that the rule allows together can be had together: the first combination that never occurs is at degree four, and the list of impossible ones is still being worked out.

    part 5 · geometry
  6. Two curves with five crossings: x⁶ + (44/31)y³ − y and its mirror. Two curves in the positive quadrant, each the zero set of a trinomial, crossing at five marked points.

    Five where four were promised

    In one unknown, a polynomial with three terms has at most two positive roots, whatever its degree. The natural guess for two equations in two unknowns, each with three terms, was two times two: four. It is wrong. Bertrand Haas found two such equations in 2002 whose curves cross five times in the positive quadrant, all five crowded within a tenth of one corner, and five turned out to be the most there can ever be.

    part 6 · geometry

All series