Past exam of the year 1 of the computer science course of the University of Oxford / 2015 / Discrete mathematics, continuous mathematics, and probability / 3 / c / ii / Solution

Write $a=qb+r$ using the Euclidean division. If $d\mid a$ and $d\mid b$, then $d\mid (a-qb)=r$. Conversely, if $d\mid b$ and $d\mid r$, then $d\mid (qb+r)=a$. Therefore $(a,b)$ and $(b,r)$ have exactly the same positive common divisors, provingFor $r=0$, this agrees with $\gcd (b,0)=b$.