Matpic
mathematics, in pictures
Series

Euclidean algorithm — the series

2 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

All series