$g_{1} = \gcd(a, b)$, $g_{2} = \gcd(b, r)$이라 하면, 최대공약수의 성질에 의해 $g_{1} \mid a$, $g_{1} \mid b$이다.
$a = bq + r$에서, $a$도 $g_{1}$의 배수, $bq$도 $g_{1}$의 배수 ($b$가 $g_{1}$의 배수이므로) 이다. 따라서 $r$도 $g_{1}$의 배수이다. (-> $g_{1} | r$)
$g_{1}$은 $b$, $r$의 공약수이고, $g_{2}$는 $b$, $r$의 공약수 중 최대이므로 $g_{1} \leq g_{2}$이다.