ユークリッドの互除法
最強です。アルゴリズムの威力をしるためのツールでもあります。
原理は実に簡単なのですが、このツールによって、いろいろな整数の性質がわかってきます。整数論するには省けない最強ツールなのです。
ユークリッドの互除法とは、
a,bを整数としたとき、a=pb+r,0≦r＜bとなる整数p,rが存在する
という定理です。
ユークリッドの互除法のなにがすごいのか。
最大公約数が高速に計算できる。
ユークリッドの互除法の式ですが、ただp,rが存在するだけでなく、なんと、
aとbの最大公約数とbとrの最大公約数は同じ
という大定理がうしろに控えているのです。aのかわりにrをつかって最大公約数を求めて良いという定理です。互除法とり、rはaとり小さい数なのでこの置き換えはものすごく威力を発揮します。
これによって、最大公約数が実に効率よく求めることができるのです。
例題
たとえば、４７３５５と４３１７３の最大公約数を求める問題があったとします。
そうやって解きますか？素因数分解すれば簡単に求まりますよ。確かに。
しかーし、素因数分解するのが簡単でないですね。それを覚悟して、いろいろ計算すると、
47355＝3×5×7×41、43173＝3×3×3×3×13×41 がわかりますから、最大公約数は3×41=123と求めることはできます。しかし、素因数分解の式をみつけるのは、かなりの労力です。
ここでユークリッドの互除法の登場です。
ユークリッドの互除法でやると、a=47355,b=43173として、
a=pb+rとなるpとrを求めます。これは、余りを使った割り算いほかなりません。ユークリッドの互除法とは余りをだず割り算のことなのです。
47355=1×43173+4182ですから、43173と4182の最大公約数を求めたら、答えが求められたも同然です。最大公約数も求めたことになります。
43173と4182の最大公約数ですが、再度どまたユークリッドの互除法です。連続して使えます。ここも利点。
43173=10×4182+1353
よって、43173と4182の最大公約数と4182と1353の最大公約数は同じ。さらに、互除法！
4182=3×1353+123
よって、4182と1353の最大公約数と1353と123の最大公約数は同じ。さらに、互除法！
1353=11*123
お、割り切れてしまいました。ここで終了です。
1353は123の倍数ですので、最大公約数は123です。つまり、47355と43173の最大公約数は123なのです。
素因数分解してから求めた最大公約数と同じ結果になることが確認できました。
まとめ
ユークリッドの互除法を使うと最大公約数を非常に効率よくもとめることができる！
[ad#foot]
コメント
ユークリッドの互除法が活躍する場所は他にもたくさんあります。これだけではありません。本当に整数論にはなくてはならない最強のツールです。
