Euclid's subtraction algorithm

Euclid wrote this algorithm in his book *Elements* (other Greek mathematicians probably knew it earlier).

The key fact: for m ≥ n, gcd(m, n) = gcd(n, m – n).

• if d divides m and n, it divides m – n;
• if d divides n and m – n, it divides their sum, m.

So both pairs have exactly the same common divisors, and the same gcd.

In pictures: if tiles of size d fit exactly along m and along n, they also fit exactly along the leftover piece m – n.

Euclid's algorithm:

• if m < n, swap them;
• if n = 0, the answer is m;
• otherwise, replace (m, n) by (n, m – n) and go again.

Example: gcd(375, 825) → gcd(825, 375) → gcd(375, 450) → … → gcd(75, 75) → gcd(75, 0) = 75, after 7 reductions. No lists needed.

But subtraction can be slow. gcd(99, 2) subtracts 2 again and again, about 49 times. In general gcd(2k + 1, 2) needs about k steps: the work still grows with the value.