= Solution
Set $(a_0,b_0)=(a,b)$. At each iteration with $b_i>0$, compute the <remainder> $r_i=a_i\bmod b_i$, then set
$$
\boxed{(a_{i+1},b_{i+1})=(b_i,r_i).}
$$
Stop at the first index $n$ with $b_n=0$ and return $a_n$. The positive second coordinates strictly decrease, so <algorithm termination> follows from the <well-ordering principle>. The equality of <greatest common divisors> established in (ii) is a <loop invariant>, and at termination it gives
$$
\boxed{a_n=\gcd(a_n,0)=\gcd(a,b).}
$$
Back to article page
