= Solution
{c}
Let $d$ be any positive <integer>. If $d$ divides $a$ and $b$, it divides the <integer linear combination> $a-qb=r$. Conversely, if $d$ divides $b$ and $r$, it divides $qb+r=a$. Thus $(a,b)$ and $(b,r)$ have exactly the same positive common <divisors>. Their greatest elements coincide:
$$
\boxed{\gcd(a,b)=\gcd(b,r).}
$$
This <greatest common divisor> invariance is the step behind the <Euclidean algorithm>; it does not require $r<b$, although that additional bound ensures the algorithm terminates. If the convention $0\in\mathbb N$ permits $r=0$, the same argument works and $\gcd(b,0)=b$ for $b>0$.
Back to article page
