GCD Shrinking Game — Subtract Smaller from Larger Until the Pair Converges

The modern Euclidean algorithm uses division with remainder, but Euclid's original version — the one in Book VII of the Elements from around 300 BCE — used only subtraction. The rule is almost embarrassingly simple: given a pair of positive integers, subtract the smaller from the larger, replace the pair, and repeat. Keep going until both numbers are equal. When they are, that common value is their greatest common divisor.

This is the GCD shrinking game. It is slower than the division version (sometimes by a lot), but it reveals the why of the algorithm more clearly. Division with remainder is just rapid subtraction; the shrinking pattern is identical. Once you see the pair collapse step by step, the identity \gcd(a, b) = \gcd(a - b, b) stops being a formula and starts being obvious.

The rule

Start with a pair (a, b) of positive integers.

1. If a = b, stop. The answer is a (which equals b).
2. If a > b, replace the pair with (a - b, b).
3. If b > a, replace the pair with (a, b - a).
4. Go to step 1.

That is it. No division, no remainders, no prime factoring. Just subtraction.

Why it works: the invariant

Every step preserves the GCD. That is, \gcd(a, b) = \gcd(a - b, b) whenever a > b > 0.

The proof in one line. If d divides both a and b, then d divides a - b (because divisibility is preserved under subtraction). So every common divisor of (a, b) is also a common divisor of (a - b, b). The argument reverses too: if d divides both a - b and b, it divides (a - b) + b = a. So the sets of common divisors of (a, b) and (a - b, b) are identical — and therefore so are their maxima.

Why this matters: each step of the game replaces the pair with a new pair that has exactly the same GCD. So the GCD of the original pair equals the GCD of the current pair, always. When the pair finally becomes (g, g), that g is both the obvious GCD of that pair and the GCD of the original.

Interactive shrinking

Play Reset a = b = Step

Why the game must end

Each step replaces the pair (a, b) with either (a - b, b) or (a, b - a). In either case, the sum a + b strictly decreases — it drops by at least 1 (actually by the smaller number). Since the sum is a positive integer at every step and keeps shrinking, it must eventually stop shrinking. The only way for it to stop is for the two numbers to become equal (at which point a - b = 0, and the algorithm halts).

More precisely: the sum a + b is a positive integer at every step, and it strictly decreases. Positive integers cannot decrease forever — there is no infinite descending chain of positive integers. So the process terminates. This is an application of the well-ordering principle: every non-empty set of positive integers has a smallest element.

Slow steps and the Fibonacci worst case

The subtraction game can be painfully slow. To compute \gcd(100, 1), you need 99 subtractions — each one reduces the pair only by 1. Compare this to the division version: 100 = 100 \times 1 + 0, one step, done.

The subtraction game's worst case is consecutive Fibonacci numbers. For the pair (F_{n+1}, F_n), the subtraction game needs exactly F_{n+1} / F_n \approx \phi \approx 1.618 subtractions per round before the numbers swap roles — which is why the Fibonacci numbers are the slowest-shrinking pairs for the division algorithm too, but much more dramatically so for subtraction.

The speedup from subtraction to division is huge. \gcd(1000, 1) takes 999 subtractions but just 1 division. This is why the division version is what we use today — and why the Indian mathematician Aryabhata described it as the kuttaka ("pulveriser"): it grinds the numbers down in great bounds instead of tiny nibbles.

A second example: \gcd(36, 24)

Walk through it yourself:

• Start: (36, 24).
• 36 - 24 = 12. Pair: (12, 24).
• Smaller on the left now. 24 - 12 = 12. Pair: (12, 12).
• Equal. Stop. \gcd(36, 24) = 12.

Three subtractions. Arithmetic check: 36 = 2^2 \times 3^2, 24 = 2^3 \times 3, shared prime factorisation is 2^2 \times 3 = 12. Same answer.

What the subtraction game reveals

The GCD is what's left when you subtract everything subtractable. Start from (a, b) and keep subtracting. The pair shrinks, but its GCD never changes. When you can't subtract any more (because both numbers are equal), the common value is the GCD. It is the invariant of the whole process — the thing that refuses to be subtracted away.

This is why the Euclidean algorithm works. Division with remainder does the same thing, faster. One division of the form a = qb + r is equivalent to q subtractions of b from a. The division version says "do all q subtractions in one shot"; the subtraction version says "do them one at a time." The answer — the final pair and its common value — is identical.

Connecting to rectangle tiling

The subtraction game has a direct geometric twin. Draw an a \times b rectangle. Cut off one b \times b square (assuming a > b). The remaining strip is (a - b) \times b. That is exactly one subtraction step, drawn as a single square removal. Keep removing one square at a time (instead of all possible squares at once, as in the division version) and you produce the subtraction game in pictures.

The rectangle-tiling visualisation uses the division version for speed. But if you remove squares one at a time, you get the subtraction game, and the final square still has side \gcd(a, b).

The one-line takeaway

Keep subtracting the smaller from the larger. The GCD never changes, the sum always shrinks, so the pair must converge to (g, g) — and that g is \gcd(a, b). Division with remainder is the same algorithm with a speed boost.

Related: Number Theory Basics · Euclidean Algorithm as Rectangle-Tiling · Why Does the Euclidean Algorithm Terminate? · Bézout's Identity · Mathematical Induction