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

>

 

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

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

 

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

 

例題


196と140の最大公約数を求めよ。

 

 

解答


196=140×1+56

140=56×2+28

56=28×2+0

よって最大公約数は28

 

 

証明


整数 a,bについて、aをbで割った商をp,余りを とおくと、

a=b×p+q

 

1:aとbの両方を割り切る整数とする。

このとき、

1はb×pを割り切るので、a-b×pも割り切る

a-b×p=qより、qも割り切る

よって、1はbとqの両方を割り切る。…①

 

逆に、

:bとqの両方を割り切る整数とする。

はb×pを割り切るので、b×p+qも割り切る

×p+q=aより、aも割り切る

よって、はaとbの両方を割り切る。…②

 

①②より

aとbの最大公約数は、bとqの最大公約数と等しい。…【終】

 

 

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

 

196140の最大公約数は、14056の最大公約数と等しい。」

14056の最大公約数は、5628の最大公約数と等しい。」

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

 

56と28の最大公約数は28であるので、

196と140の最大公約数も、28であると言えます。

By