Euclidean algorithm halts with all-and-only commensurable inputs

show: the euclidean algorithm halts if, and only if, it is given commensurable quantities

Let $a,b>0$ be two magnitudes (or lengths). “Commensurable” means there is a third magnitude $d>0$ and positive integers $m,n$ with

$$ a = m d,\quad b = n d, $$

i.e., $a$ and $b$ are integer multiples of a common measure $d$. The Euclidean algorithm (in the modern form using division with remainder, or equivalently the subtractive form) produces a sequence of remainders

$$ r_0 := a,\quad r_1 := b,\quad r_{i+1} := r_{i-1}\bmod r_i, $$

and halts exactly when some $r_k$ divides $r_{k-1}$ giving $r_{k+1}=0$; the last nonzero remainder is then a common measure.

We prove the equivalence:

(⇒) If the Euclidean algorithm halts on $a,b$, then $a$ and $b$ are commensurable. Suppose it halts in finitely many steps with last nonzero remainder $r_k$, so that $r_{k-1} = q_{k} r_k$ and the next remainder is zero. By the division relations backwards,

$$ r_k\mid r_{k-1},\quad r_k\mid r_{k-2},\ \dots,\ r_k\mid r_1=b,\quad\text{and }r_k\mid r_0=a. $$

Thus $a = M r_k,\ b = N r_k$ with integers $M,N$; so $r_k$ is a common measure and $a,b$ are commensurable.

(⇐) If $a$ and $b$ are commensurable, say $a = m d,\ b = n d$ with $m,n\in\mathbb{Z}_{>0}$, then the Euclidean algorithm on $a,b$ reduces to the usual integer Euclidean algorithm on $m,n$ with unit $d$: each division step

$$ r_{i-1} = q_i r_i + r_{i+1} $$

when scaled by $d^{-1}$ becomes an integer division among the corresponding integers. Since the Euclidean algorithm on positive integers $m,n$ terminates in finitely many steps (the remainders form a strictly decreasing sequence of nonnegative integers), the algorithm on $a,b$ also terminates—yielding as last nonzero remainder $(\gcd(m,n))d$, a common measure.

Therefore the Euclidean algorithm halts on $a,b$ if and only if $a$ and $b$ are commensurable. ∎