Euclid’s Algorithm／ユークリッドのアルゴリズム（ユークリッドの互除法）

私たちに必要なのは、2つの数字の最大公約数を見つける方法です。

もしかすると、皆さんはすでに小学校の頃に、基本的な考え方は学んだかもしれません。例えば、 (20 = 5times 4)、(15 = 5times 3)であり、20と15の最大公約数は5となります。しかし、問題のサイズが大きくなったときにどのくらい大変な問題であるのかを今一度認識しなくてはなりません。この場合そこまで難しい問題ではありませんが、どのように行うかを学ぶことは非常に有意義です。

Euclid(ユークリッド)は、幾何学への偉大な功績により、古代ギリシアの数学者の中で最も有名であり、減算の繰り返しによる最大公約数を発見するアルゴリズムも発見しています。このユークリッドのアルゴリズムを、126と72の最小公倍数の例を通して見てみましょう。まず以下のように、大きな数字から、小さな数字を順番に引いていきます。

(126 – 72 = 54)
(72 – 54 = 18)
(54 – 18 = 36)
(36 – 18 = 18)
(18 – 18 = 0)

そして、最後の0でない値が、最大公約数となります。(126 = 7times 18)と、(72 = 4times 18)のようになります。そのため(mathrm{gcd}(126,72) = 18)と書くことができます。途中で (54 = 3times 18)とすぐ気がつくかもしれませんが、その場合数ステップ早く計算を終わらせることができます。

ユークリッドのアルゴリズムは、美しく視覚化することができます。(mathrm{gcd}(x,y))を見つけるために、(xtimes y)の四角形を作ります。そして、その四角形を入りうるる最も大きな正方形（1つもしくは複数の、辺の長さが(x)と (y)の小さい方の正方形)で埋めていきます。

このアルゴリズムは最初の週で説明したような、計算複雑性という観点から効果的で、桁の大きさに関して多項式時間的な時間増加で解くことが可能です。