ユークリッドの互除法で最大公約数を求める

最大公約数を求めるには、素因数分解しながら共通部分を掛け合わせる方法の他に、単純な割り算と引き算を繰り返す方法もあります。これは、アルゴリズムの原点とも言われるユークリッドの互除法と呼ばれる方法で、以下のようにして最大公約数を求めます。

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

  • 二つの整数x, y（x >= y)に対し、x / yの演算を行いその余り（剰余）をrとする（y = 0なら最大公約数はa）
  • r = 0（xがyで割り切れる）なら、yが最大公約数
  • x = y, y = rとして1に戻る

つまり、a, bにb とbとa / bの余りを入れていく演算を割り切れるようになるまで続けるわけですね。ユークリッドの互除法を使うと、特にa, bが巨大な数の場合は素因数分解で最大公約数を求めるよりも計算回数を劇的に減らすことができます（巨大な数の素因数分解は、その困難さが暗号を支える数学的な理論背景になるほど「重い」計算）。

では、なぜこうなるのでしょう。最初から「余り」だとわかりにくいので、まずは二つの整数x, yと（x - y）について考えてみましょう。

二つの整数x, y（x >= y）の任意の公約数をcとするなら、以下の関係が成り立ちます。

x = ac
y = bc

(x - y) = ac - bc = (a - b)c

つまり、「x, y, (x - y)の最大公約数はcとなる（任意の公約数で成り立つ以上、その最大の場合である最大公約数でも成り立つ）」わけです。このことは、xとyの最大公約数を求めるには、yと(x - y)の最大公約数を求めれば良い、ということを示しています。大きな数よりは小さな数の方が扱い安いので、ありがたいですね。

さらに、yと(x - y)についても上の関係は成り立ちますから、「yと(x - y)の大きい方を新たにx、小さい方を新たにy」とすれば、同様に「xと(x - y)の最大公約数」からその最大公約数が求まりますね。そして、その最大公約数は最初のxとyの最大公約数にもなるはずです（上の式で公約数cはいじってない）。

ユークリッドの互除法のプログラム

少し、混乱してきたので、ユークリッドの互除法のアルゴリズムをJavaScriptのコードにまとめて実際に計算してみましょう。

以下のフォームは、二つの整数x, yを入力して計算ボタンをクリックすると、テキスト欄に「xと(x - y)」の計算結果をxに前のy、yに前のx - yを代入しながら列挙していきます。

// aとbの最大公約数の計算過程を表示
function getGcm(a, b) {

	var list = document.getElementById("list");

	list.value = "";

	while (a > 0 && b > 0) {

		// a > bにする
		if (b > a) {

			c = a;

			a = b;
			b = c;

		}

		list.value += a + "," + b + "\n";

		c = b;

		// a = b, b = a - bとし、再計算
		b = a - b;
		a = c;

	}

}
x= y=

たとえば、160と48で試してみると

160,48
112,48
64,48
48,16
32,16
16,16

となって最大公約数16が求まりますね。

さて、上の結果を見てみると、最初は「160から48を引き続けている」のがわかると思います。そして、160から48を引けなくなると、その余りに対して演算が続けられます。

これは、xとyの小さい方は(x - y)がy以下になるまで「そのまま残る」からですね。そして、xがyで引けなくなると、そこに残るのは「x / yの剰余」ということになり、これは「二つの整数xとy（x >= y）の最大公約数は、yとx /yの剰余の最大公約数に等しい」ことを意味しています。
つまり、「yとx / yの剰余」を求める計算を（x = y, y=rとしながら）続ければ最大公約数が求まり、それこそが「ユークリッドの互除法」というわけです。

では、最後に上のスクリプトの計算を最初からyとx / yの余りで行うようにしてユークリッドの互除法で最大公約数を求めることにしてみましょう。

// aとbの最大公約数の計算過程を表示
function getGcm2(a, b) {

	var list2 = document.getElementById("list2");

	list2.value = "";

	while (b < 0) {

		// a > bにする
		if (b > a) {

			c = a;

			a = b;
			b = c;

		}

		list2.value += a + "," + b + "\n";

		c = b;

		// a = b, b = a / bの剰余とし、再計算
		b = a % b;
		a = c;

	}

	return a;

}
x= y=