Past exam of the mathematics course of the University of Oxford / 2021 / Prelims / Mathematics IV resit / 7 / a / Solution

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: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$.