euclid-step-keeps-gcd

Sun Sep 13 2026

The Euclidean algorithm replaces the pair $(a, b)$ by $(b, r)$, where $a = q b + r$ and $0 \le r < b$, and repeats until the remainder is 0. It computes $\gcd(a, b)$ only if every step preserves it:

$\gcd(a, b) = \gcd(b, r).$

Where I got stuck

Picture $a$ as a strip cut into $q$ segments of length $b$ and a leftover of length $r$. Let $d = \gcd(a, b)$, the biggest block that tiles both $a$ and $b$. The block $d$ tiles the whole strip and tiles each $b$ segment, so it tiles the leftover:

$r = a - q b = (k_1 - q k_2)\, d .$

So $d$ divides both $b$ and $r$. I read that as "$d$ is the gcd of $(b, r)$ as well", equality, done. When the write-up said this only proves $\gcd(a, b) \le \gcd(b, r)$, I pushed back for three turns. I had started with $d$ being the gcd, not some factor, so where could an inequality come from?

What the argument actually used

One property of $d$: it divides $a$ and $b$. It never used that $d$ is the largest such number. So any block with that property survives the same argument, and the conclusion is only what is true of every such block: $d$ is a common divisor of $(b, r)$. Being the gcd of $(a, b)$ is a fact about the pair $(a, b)$. It says nothing about how the pair $(b, r)$ ranks its divisors.

The counterexample is to the inference, not to the number. Take $a = 24$, $b = 18$, so $24 = 1 \cdot 18 + 6$. The block 3 tiles 24 and 18, so by the same argument it tiles $r = 6$. All true, and $\gcd(18, 6) = 6$, not 3. The argument's shape cannot tell 3 from 6, so it cannot conclude "greatest" for either.

What the strip argument proves, exactly: every common divisor of $(a, b)$ is a common divisor of $(b, r)$. Hence $\gcd(a, b) \le \gcd(b, r)$, and nothing more.

The other direction

The way it closed: suppose $(b, r)$ had a common divisor $e$ bigger than $d$. Then $e$ divides $b$ and $r$, so it divides $q b + r = a$. That makes $e$ a common divisor of $(a, b)$ bigger than the greatest one, which is impossible. So no common divisor of $(b, r)$ exceeds $d$, and with the first half that is equality.

Written out directly it is the same line. Take any $e$ dividing both $b$ and $r$, say $b = e m_1$ and $r = e m_2$. Then

$a = q b + r = e\,(q m_1 + m_2),$

so $e$ divides $a$ too. Every common divisor of $(b, r)$ is a common divisor of $(a, b)$, which gives $\gcd(b, r) \le \gcd(a, b)$.

The two directions use different halves of the same equation. The first subtracts, $r = a - q b$, and the second adds back, $a = q b + r$. Each is one line, and neither alone is the lemma. On the counterexample pair the chain runs $(24, 18) \to (18, 6) \to (6, 0)$ with gcd 6 at every stage. On a coprime pair, $(12, 5) \to (5, 2) \to (2, 1) \to (1, 0)$, the gcd is 1 throughout, which is what makes the back-substitution in units-mod-n-coprime-and-totient land on 1.

The general lesson: an argument that uses only a shared property cannot single out the extreme element. To prove "$d$ is the greatest" the word greatest has to enter somewhere, and here it enters only through the reverse direction. Same shape as one-to-one-proof-converse-trap: one direction proved, both directions claimed.