The Euclidean algorithm is the granddaddy of all algorithms, because it is the oldest nontrivial algorithm that has survived to the present day.

— Donald Knuth, The Art of Computer Programming, vol. 2 (1969)

You have two rods, one 252 cm long and the other 105 cm, and you want the longest ruler that measures both exactly, a whole number of times. In today’s language you want the greatest common divisor, $\gcd(252,105)$. You could list all the divisors of each number and look for the largest common one, but with big numbers that is impractical. In Book VII of the Elements, Euclid teaches a much faster way.

Subtract the smaller from the larger

Euclid’s idea, in Propositions VII.1 and VII.2, is simple: any ruler that measures both rods also measures their difference. So instead of looking for the common measure of 252 and 105, we can look for it for 105 and $252-105=147$. And then for 105 and $147-105=42$. Always subtract the smaller from the larger, until the two become equal:

$$(252,105)\to(147,105)\to(42,105)\to(42,63)\to(42,21)\to(21,21).$$

Both became 21. That is the greatest common divisor. The Greeks called the procedure anthyphairesis, “reciprocal subtraction”.

The version with divisions

Subtracting the same number several times is dividing. Gathering the repeated subtractions into a division with remainder makes the algorithm shorter:

$$\begin{aligned}252&=2\cdot105+42\\105&=2\cdot42+21\\42&=2\cdot21+0\end{aligned}$$

The last non-zero remainder is the greatest common divisor:

$$\boxed{\gcd(252,105)=21.}$$

Why it works

If $a=qb+r$, then:

  • every number dividing $a$ and $b$ also divides $r=a-qb$;
  • every number dividing $b$ and $r$ also divides $a=qb+r$.

The pairs $(a,b)$ and $(b,r)$ have exactly the same common divisors, so $\gcd(a,b)=\gcd(b,r)$. And why does the algorithm stop? Because the remainders are positive integers that decrease at each step, $42>21>0$, and a sequence of positive integers cannot decrease forever. At some point the remainder is zero, and $\gcd(d,0)=d$.

The algorithm is fast. The Frenchman Gabriel Lamé proved in 1844 that the number of divisions never exceeds five times the number of digits of the smaller of the two numbers. For hundred-digit numbers, at most 500 divisions are needed.

Working back through the steps

The calculation also lets us write the gcd as a combination of the two numbers. Go back from the bottom up:

$$\begin{aligned}21&=105-2\cdot42\\&=105-2\cdot(252-2\cdot105)\\&=5\cdot105-2\cdot252.\end{aligned}$$

Check: $525-504=21$. In general, for any $a$ and $b$, there are integers $x$ and $y$ with $ax+by=\gcd(a,b)$. This is Bézout’s identity, and the procedure of working back is called the extended Euclidean algorithm.

Exercise: find the greatest common divisor of 391 and 299.

$391=1\cdot299+92$, $299=3\cdot92+23$ and $92=4\cdot23+0$. The gcd is 23. Indeed, $391=17\cdot23$ and $299=13\cdot23$.

Exercise: simplify the fraction 252/105 and write 1 as a combination of 12 and 5.

Dividing both terms by the gcd, 21: $\frac{252}{105}=\frac{12}5$. Now $12=2\cdot5+2$ and $5=2\cdot2+1$. Working back: $1=5-2\cdot2=5-2\cdot(12-2\cdot5)=5\cdot5-2\cdot12$. Check: $25-24=1$.

Sources: Elements, Propositions VII.1 and VII.2, D. E. Joyce’s edition · Donald E. Knuth, The Art of Computer Programming, vol. 2, section 4.5.2 · Gabriel Lamé, “Note sur la limite du nombre des divisions dans la recherche du plus grand commun diviseur”, Comptes rendus 19 (1844).

All topics on Euclid · ← Algebra done with squares and rectangles · The primes never run out →

Image credits.