$a$, $b$, $q$, $r$ を整数とし, $$ a=bq+r $$ を満たすとする. このとき, $$ \gcd(a,\,b) = \gcd(b,\,r) $$ が成り立つことを証明せよ.
解答例 1
$d=\gcd(a,\,b)$, $d'=\gcd(b,\,r)$ とおく. $r=a-bq$, $d\mid a$, $d\mid b$ より, $d\mid r$. ゆえに, $d\mid d'$. 逆に, $a=bq+r$, $d'\mid b$, $d'\mid r$ より, $d'\mid a$. ゆえに, $d'\mid d$. したがって, $d\mid d'$ と $d'\mid d$ とから, $d=d'$ がいえる.
最終更新日：2011年11月02日