A procedure for finding the greatest common divisor of two whole numbers by repeatedly replacing the larger with its remainder on division by the smaller. It is about 2,300 years old, it is still the method used in practice, and modern public key cryptography depends on an extension of it.

The algorithm applied geometrically: the largest square that fits the rectangle is removed repeatedly, and the last square that fits exactly gives the common measure.
The algorithm applied geometrically: the largest square that fits the rectangle is removed repeatedly, and the last square that fits exactly gives the common measure.Credit: Christian.Mercat (CC BY-SA 3.0).

To find the greatest common divisor of two numbers, divide the larger by the smaller and keep the remainder. Replace the pair with the smaller number and that remainder, and repeat. When the remainder reaches zero, the last non-zero remainder is the answer.

For 1071 and 462: 1071 leaves 147 on division by 462; 462 leaves 21 on division by 147; 147 leaves 0 on division by 21. The greatest common divisor is 21.

The original form in the Elements uses repeated subtraction rather than division, which is the same procedure with the divisions written out one subtraction at a time. Applied to lengths rather than numbers it finds a common measure, which is how the Greeks framed it.

The whole proof rests on one observation: any number dividing both a and b also divides the remainder when a is divided by b, and conversely any number dividing b and that remainder also divides a.

So the pair before each step and the pair after it have exactly the same set of common divisors, and therefore the same greatest one. The quantity being sought never changes while the numbers shrink.

Termination is immediate. Remainders are non-negative and strictly smaller at each step, so a decreasing sequence of non-negative integers must reach zero. When it does, the remaining number divides the previous one and is the largest that divides both.

Euclid as imagined in a painting of about 1474. The algorithm appears in Book VII of the Elements, though it was almost certainly known before he compiled it.
Euclid as imagined in a painting of about 1474. The algorithm appears in Book VII of the Elements, though it was almost certainly known before he compiled it.Credit: Justus van Gent (Public domain).

The algorithm appears as Propositions 1 and 2 of Book VII of Euclid's Elements, compiled around 300 BCE, and again in Book X for geometric magnitudes.

A papyrus fragment of the Elements from the third or fourth century CE. The text was copied continuously for two millennia, which is part of why the algorithm was never lost.
A papyrus fragment of the Elements from the third or fourth century CE. The text was copied continuously for two millennia, which is part of why the algorithm was never lost.Credit: University of Pennsylvania Museum of Archaeology and Anthropology (CC BY-SA 4.0).

It is generally thought to predate Euclid, who was compiling and organising existing results rather than inventing them, and versions appear independently in Chinese and Indian mathematics. It is commonly described as the oldest algorithm still in everyday use, and the description is fair.

The algorithm is much faster than it looks, and the worst case is exactly identified.

Gabriel Lamé proved in 1844 that the number of division steps never exceeds five times the number of decimal digits of the smaller number. This is generally regarded as the first analysis of the running time of an algorithm.

The worst case occurs for consecutive Fibonacci numbers, where every quotient is 1 and each step removes as little as possible. That the extreme case of a number-theoretic algorithm is the Fibonacci sequence is a genuinely surprising connection, and it is why the number of steps grows only with the logarithm of the input.

In practice the algorithm handles numbers with hundreds of digits in negligible time, which is what makes the cryptographic application possible.

Running the steps backwards expresses the greatest common divisor as a combination of the two original numbers, with whole number coefficients. That such coefficients exist is Bézout's identity, and the extended Euclidean algorithm computes them.

The consequence that matters is modular inverses. If two numbers have greatest common divisor 1, the extended algorithm produces the multiplicative inverse of one modulo the other, and it is the only practical way to do so for large numbers.

RSA key generation depends on exactly this step: the private exponent is the modular inverse of the public exponent, and it is computed with the extended Euclidean algorithm. The same computation underlies elliptic curve cryptography and the arithmetic of finite fields used in error correcting codes.

The algorithm also generates the continued fraction expansion of a ratio, since the successive quotients are precisely its terms, which links it to best rational approximation.

The Euclidean algorithm is the standard example of an algorithm that is simple to state, provably correct, provably fast, and genuinely useful, all at once. It also demonstrates something about mathematics that is easy to overlook: a procedure written down for measuring line segments before the invention of algebra turned out, unchanged, to be a load-bearing component of the systems that secure modern communication.