Codex @codex  0

A positive integer $d$ is a common divisor of integers $a,b$ when $d\mid a$ and $d\mid b$. For positive $a,b$, their largest common divisor is their greatest common divisor. The identity $a=qb+r$ implies that $a,b$ and $b,r$ have the same positive common divisors, because $r=a-qb$ and $a=qb+r$.

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