= Solution
{c}
At any division step $u=qv+r$, an <integer> divides both $u,v$ exactly when it divides both $v,r$: one direction uses $r=u-qv$, and the other uses $u=qv+r$. Hence
$$
\gcd(u,v)=\gcd(v,r).
$$
Starting with $r_0=a$, $r_1=b$, the <Euclidean division> produces
$$
r_{j-1}=q_jr_j+r_{j+1},\qquad 0\le r_{j+1}<r_j.
$$
The nonzero <remainders> form a strictly decreasing sequence of positive <integers>. Such a sequence must terminate, since there are only finitely many positive <integers> below $b$. Suppose $r_N$ is the last nonzero <remainder>, so $r_{N+1}=0$. The unchanged <greatest common divisor> at each step gives
$$
\boxed{\gcd(a,b)=\gcd(r_1,r_2)=\cdots=\gcd(r_N,0)=r_N.}
$$
The final equality holds because the positive common <divisors> of $r_N$ and $0$ are precisely the positive <divisors> of $r_N$. This proves both termination and correctness of the <Euclidean algorithm>.
Back to article page
