$$ \newcommand\bm[1]{\boldsymbol{#1}} \renewcommand\limsup{\varlimsup} \renewcommand\liminf{\varliminf} $$

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

©2003-2011 よしいず