ユークリッドの互除法

読み：ユークリッドのごじょほう
品詞：名詞

ユークリッド幾何学などで知られる古代ギリシャの数学者ユークリッド(エウクレイデス)が、著書である原論に書き残した最大公約数の求め方の通称。

実際の発案はユークリッドではなく、更に前のピタゴラスの時代であるとも言われている。

計算方法

自然数aとbに対する最大公約数を求めることとし、それを数式でgcd(a,b)と書くとする。

この時、a>b>0とし、a÷bの剰余をr≧0とすると、常に次の式が成立する。

gcd(a,b)=gcd(b,r)

a>b>r

この式が成立する理由は次のとおり。

まずa÷b=q…r[式ア]とし、移項してr=a−q×b[式イ]とする。
gcd(a,b)はaとbを割り切ることが可能で、また前式イからrも割り切ることが可能。ゆえにgcd(a,b)はbとrの公約数でもある。そして常に、gcd(a,b)≦gcd(b,r)が成り立つ[条件ア]。
また前式アからgcd(b,r)はaを割り切ることが可能と求められ、ゆえにgcd(b,r)はaとbの公約数である。そして常にgcd(b,r)≦gcd(a,b)が成り立つ[条件イ]。
条件アと条件イから導かれる結論は、gcd(a,b)=gcd(b,r)である。

この方法での実際の求め方を考えてみる。上の命題により、gcd(a,b)とgcd(b,r)が等しいことを求められたので、gcd(a,b)を求めるにはgcd(b,r)を求めれば良いことになる。

そしてもし、gcd(b,r)がなお分からなければ、bをrで割って同様に計算を継続させればよく、これを繰り返せば最終的にはgcd(x,0)、x>0、となり、そしてgcd(x,0)=xであるので、これにより最小公倍数を求めることができる。以上、証明終わり。

例えば、gcd(19050,16637)を考えてみる。ここまで大きな数になると素因数分解も困難になるため通常の方法では最大公約数は求めづらく、ユークリッドの互除法が活躍できる。

19050=1×16637+2413 ∴gcd(19050, 16637)=gcd(16637, 2413)
16637=6×2413+2159 ∴gcd(16637, 2413)=gcd(2413, 2159)
2413=1×2159+254 ∴gcd(2413, 2159)=gcd(2159, 254)
2159=8×254+127 ∴gcd(2159, 254)=gcd(254, 127)
254=2×127+0 ∴gcd(254, 127)=gcd(127, 0)

よって、19050と16637の最小公倍数は127であることが求められた。

これをコンピュータープログラムへ実装する場合、aとbが一致するまでループさせ、大きい方から小さい方を引く、ということを繰り返す。両者が一致したとき、それが最大公約数である。

gcd.c (C言語による例)

用語の所属