One tool we are going to need in our toolbox is a way to find the greatest common divisor (GCD) of two numbers.

You probably learned the basic idea in elementary school; since (20 = 5times 4) and (15 = 5times 3), the greatest common divisor of 20 and 15 is 5. But once again, we need to worry about how hard such a problem is as the problem size grows; in this case, it turns out not to be particularly difficult, but it is worth learning how to do it.

Euclid himself, perhaps the most famous of the ancient Greek mathematicians for his work on geometry, developed (or at least wrote down) an algorithm for GCD, based on repeated subtraction. The algorithm is best explained by example, so let’s look for the GCD of 126 and 72. Begin by subtracting the smaller number from the larger one, and repeating until we reach zero:

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

and the last non-zero number is our GCD. (126 = 7times 18) and (72 = 4times 18), so (mathrm{gcd}(126,72) = 18). You may well have recognized that (54 = 3times 18), so we could have terminated the algorithm a couple of steps earlier.

The algorithm has a beautiful visualization. To find (mathrm{gcd}(x,y)), create a rectangle that is (xtimes y). Begin filling it with the largest squares that will fit (one or more squares the size of the smaller of (x) and (y)). In the remaining rectangle, perform the same operation. Repeat until the original rectangle is filled. The edge length of the smallest size of square is the GCD. The Exercise in the next Step lets you play with the algorithm and see for yourself how it works.

This algorithm is efficient in the terms that we described in the first week, when we talked about computational complexity; it will run in time that is polynomial in the number of digits in the numbers.

ユークリッドのアルゴリズム（ユークリッドの互除法）

私たちに必要なのは、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)の小さい方の正方形)で埋めていきます。

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