《証明》$a,b$の最大公約数$\text{GCD}(a,b)$を$d$、$b,r$の最大公約数$\text{GCD}(b,r)$を$d’$とする。題意を証明するためには$d=d’$を示せば良い。$a=bq+r$について$bq$を移項すると$a-bq=r$となる。仮定より、この左辺は$d$の倍数だから、右辺の$r$も$d$の倍数となる。このことから、$d$は$b,r$をともに割り切るから、$d$はそれらの最大公約数$\text{GCD}(b,r)$と同じかそれより小さくなければならない。\text{GCD}(b,r)=d’$$が必要である。仮定より、$a=bq+r$の右辺は$d’$の倍数だから、左辺の$a$も$d’$の倍数となる。このことから、$d’$は$a,b$をともに割り切るから、$d’$はそれらの最大公約数$\text{GCD}(a,b)$と同じかそれより小さくなければならない。d’=\text{GCD}(b,r)$$が必要である。\text{GCD}(b,r)$が成立するためには$\text{GCD}(a,b)=\text{GCD}(b,r)$でなければならない。成り立つことが示された。(2020/02/08記)風邪やウイルスが流行っていますね。手洗いうがいの励行と、良質な食事と睡眠を心掛けて生活しましょう!当サイトについてのご意見・ご要望はトップメニューバーの「その他」→「お問い合わせ」のページからお寄せ下さい。当サイトを閲覧するときはJavaScriptを有効化して下さい。スマートフォンの場合、ブラウザや機種、インターネット環境によってはMathjaxの立ち上がりにやや時間が掛かることがありますので、ご理解下さい。当サイトへのリンク付けは基本的に自由です。任意としますが、その際は管理人まで一声掛けて頂けると更新の励みになります。投稿記事・固定ページを含むすべての内容の著作権は当サイトに帰属します。当サイトの記事等の内容を引用する際は必ず出典とリンク(URL)を記載して下さい。