ユークリッドの互除法とは

ユークリッドの互除法とは・・・

「２つの整数の最大公約数を求める手段」の一つです。

それでは例題を見てみましょう。

１９６と１４０の最大公約数を求めよ。

１９６＝１４０×１＋５６

１４０＝５６×２＋２８

５６＝２８×２＋０

よって最大公約数は２８

整数 ａ，ｂについて、ａをｂで割った商をｐ，余りを ｑとおくと、

ａ＝ｂ×ｐ＋ｑ

ｒ₁：ａとｂの両方を割り切る整数とする。

このとき、

ｒ₁はｂ×ｐを割り切るので、ａ－ｂ×ｐも割り切る。

ａ－ｂ×ｐ＝ｑより、ｑも割り切る。

よって、ｒ₁はｂとｑの両方を割り切る。…①

逆に、

ｒ_２：ｂとｑの両方を割り切る整数とする。

ｒ_２はｂ×ｐを割り切るので、ｂ×ｐ＋ｑも割り切る。

ｂ×ｐ＋ｑ＝ａより、ａも割り切る。

よって、ｒ_２はａとｂの両方を割り切る。…②

①②より

ａとｂの最大公約数は、ｂとｑの最大公約数と等しい。…【終】

このことを使って「【問題】１９６と１４０の最大公約数を求めよ。」について考えてみると、

「１９６と１４０の最大公約数は、１４０と５６の最大公約数と等しい。」

「１４０と５６の最大公約数は、５６と２８の最大公約数と等しい。」

ということが成り立ちます。

５６と２８の最大公約数は２８であるので、

１９６と１４０の最大公約数も、２８であると言えます。

By スタッフ01