Long before there were machines to run them, there were algorithms. The oldest one we still use every day was written down by a geometer in Alexandria more than two thousand years ago — a recipe so exact that a person, a pebble-abacus, or a silicon chip will all arrive at the same answer by the same steps. Knuth opens The Art of Computer Programming with it, because it is the perfect specimen of what an algorithm is: finite, definite, effective, and blind to the meaning of the numbers it grinds.
The problem is deceptively humble. Given two whole numbers, find the greatest common divisor — the largest number that divides both without remainder. Think of it physically. You have two lengths, say a plank of 1071 units and a plank of 462. You want the longest single ruler that can measure both planks a whole number of times, with nothing left over. That ruler is invisible until you find it, and Euclid's method is how you conjure it into view.
"We represent an algorithm as a precise, unambiguous, mechanical procedure — and then we ask, coldly, how much work it costs." — after D. E. Knuth, TAOCP Vol. 1, §1.1
I · AnthyphairesisThe subtraction that never lies
Euclid's insight is a single, self-evident fact: any number that divides both a and b also divides their difference a − b. So the common measure of the two planks is unchanged if you lay the shorter plank against the longer and saw off its length. Repeat, always subtracting the smaller from the larger, and the numbers shrink while their hidden common ruler stays exactly the same. When the two lengths finally become equal, that equal length is the greatest common divisor. The Greeks called this repeated mutual subtraction anthyphairesis.
Subtracting one at a time is honest but slow. If the smaller plank fits into the larger seven times, why saw seven times when you could divide once? Replace repeated subtraction with a single division and a remainder — a = q·b + r — and you have Knuth's Algorithm E, the modern form. Each step trades the pair (a, b) for the smaller pair (b, a mod b), until the remainder is zero. The last nonzero remainder is the ruler you were looking for.
Each square carved from the rectangle is one subtraction. A whole strip of equal squares is one division. When the last strip tiles perfectly, the side of those golden squares is the greatest common divisor — the invisible ruler made visible.
II · The Golden Worst CaseWhy Fibonacci breaks the saw
Load the pair 233 & 144 and watch the rectangle spiral inward, shedding exactly one square at every generation. These are consecutive Fibonacci numbers, and they are Euclid's mortal enemies: for a given size of input, no pair forces the algorithm to take more steps. This is not a coincidence. Gabriel Lamé proved in 1844 that the number of division steps never exceeds five times the number of decimal digits of the smaller number — and the Fibonacci pairs are precisely the case that saturates the bound. It is, arguably, the first theorem ever proved about the running time of an algorithm.
The rectangle of a Fibonacci pair carves itself into a perfect cascade of squares — the same cascade that draws the golden spiral. Slowness and beauty, from the same seed.
Contrast that with 48 & 36: a couple of fat strips and it collapses to 12. Or the coprime pair 97 & 41, which grinds all the way down to squares of side 1 — the algorithm's way of announcing that the two lengths share no common ruler at all but the trivial one.
III · Bézout's GhostThe ruler was a combination all along
Euclid tells you the greatest common divisor exists. A small bookkeeping addition — running the remainders backward — tells you something stranger and more useful: that the divisor g can always be written as a whole-number combination of the two originals, a·s + b·t = g. This is Bézout's identity, and the coefficients s and t fall out for free from the extended algorithm. The scale in the instrument weighs it for you: the single weight g on the left is balanced, exactly, by adding s copies of a to t copies of b on the right.
That identity is not a curiosity. It is the mathematical bedrock of modular inverses, and therefore of RSA keys, of the Chinese Remainder Theorem, of every scheme that needs to undo multiplication in modular arithmetic — the machinery you will meet again in Wing II: The Engine of Chance. The oldest algorithm quietly underwrites the newest cryptography.
"An algorithm must be seen to be believed." — D. E. Knuth
So work the instrument. Change the lengths. Switch the saw from subtraction to division and feel the difference between the ancient method and the modern one. Push it to the Fibonacci edge and count the steps. Every time, the same invisible ruler emerges from the same finite, definite, effective procedure — the thing Knuth spent three thousand pages teaching us to reason about with care.