高校数学「数と式」ユークリッドの互除法

高校数学「数と式」ユークリッドの互除法

★ユークリッドの互除法(Euclidean Algorithm)

ａ＞ｂとして、ａ÷ｂの余りを出す。その余りでｂを割る。さらにその余りで…
このように、余りがゼロになるまで次々と割り算をしていきます。
余りがゼロになったときの割る数がａ，ｂの最大公約数になる。
という方法です。

例：
(i) ８と６の場合

８÷６＝１・・・２
６÷２＝３

これで余りがゼロになったので、８と６の最大公約数は２と求められました。


(ii) ７００と３１５の場合

７００÷３１５＝２・・・７０
３１５÷７０＝４・・・３５
７０÷３５＝２

よって、最大公約数は３５


◆関連項目
一次不定方程式の解き方
高校数学数と式まとめ


江間淳の書籍はこちら
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
　20年以上の実績。全学年、英・数・理をはじめ全教科対応
　　最高級の指導を提供します！メール添削も好評です！

プロ家庭教師の江間です。　　　　ＡＥ個別学習室(えまじゅく)
http://www.a-ema.com/k/　　　　 http://www.a-ema.com/j/
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−