ユークリッドの互除法

ユークリッドの互除法とは、2つの自然数の最大公約数を求めるアルゴリズムである。

概要

最大公約数を求めたい2つの整数を m、n （どちらか一方が0以上の整数、もう一方が正の整数）とすると、以下のような手順で、m と n の最大公約数を求めることが出来る。

1. n = 0の場合、m を最大公約数として終了する。n ≠ 0（すなわち n > 0）の場合、2.へ進む。
2. m ÷ n の剰余を r とする。
3. m に n、n に r を代入する。
4. 1.へ戻る。

剰余の代わりに減算を用いる方法もあるが、両者の間に本質的な差異は何も無い。

ユークリッドの互除法は最古のアルゴリズムとしても有名だが、優れたアルゴリズムと言われる所以は手数の少なさにある。アルゴリズムを終了するのに十分な手数は、n の桁数に比例するのである。具体的に言うと、n の10進桁数の5倍だけ行うまでに、結果がわかる。紀元前の時代にここまで優れたアルゴリズムが存在したことは注目に値する。

例

728と693の最大公約数を求める。

	m	n	r
(1)	728	693	35
(2)	693	35	28
(3)	35	28	7
(4)	28	7	0
(5)	7	0	-

よって、728と693の最大公約数は、7。

なお、m < n のとき、m ÷ n → 0 余り m であるため、m、n の大小関係に関して特に制約は無い。

プログラミング言語での実装例

ここではC言語での実装例を記載する。他のプログラミング言語においても、ループ処理、再帰処理等が実装可能であれば大体同じようにして実装出来る。なお、引数 m、n については前提条件（どちらか一方が0以上の整数、もう一方が正の整数）を必ず満たしているものとする。

ループ処理による実装例

int getGCD(int m, int n) {
    while (n != 0) {
        int r = m % n;
        m = n;
        n = r;
    }
    return m;
}

再帰処理による実装例

int getGCD(int m, int n) {
    if (n == 0) {
        return m;
    } else {
        return getGCD(n, m % n);
    }
}

再帰処理及び三項演算子による実装例

int getGCD(int m, int n) {
    return n == 0 ? m : getGCD(n, m % n);
}

拡張ユークリッドの互除法

a,bの最大公約数をdとして、ユークリッドの互除法の逆をたどることでax+by=dとなる整数x,yを全て求めることができる。これはa,bが互いに素、つまりd=1である時に特に有用。

a=728、b=693とする。

728=693+35

693=35×19+28

35=28+7

28=7×4+0

最大公約数が7と分かったので逆をたどる。

7=35-28

=35-(693-35×19)=35×20-693

=(728-693)×20-693=728×20-693×21

以上より、x=20、y=-21が候補の一つ。

728x+693y=7なので、728x-728×20+693y-693×(-21)=0

7(104(x-20)+99(y+21))=0

104,99は互いに素なので、kを整数として、x-20は99k、y+21は104k。

以上より、x=99k+20、y=104k-21の形で表される。

多項式のユークリッド互除法

多項式に関しても整数と同じように最大公約多項式や最小公倍多項式といったものが定義できる。

例　2x⁹-x⁸-2x+1　と　x⁴+x³-x-1 の最大公約多項式を実数係数の範囲で求める。

(2x⁹-x⁸-2x-1)=(x⁴+x³-x-1)(2x⁵-3x⁴+3x³-x²)+(2x³-x²-2x+1)

(x⁴+x³-x-1)=(2x³-x²-2x+1)(x/2+3/4)+7/4(x²-1)

(2x³-x²-2x+1)=7/4(x²-1)(8x/7-4/7)+0=(x²-1)(2x-1)+0

最大公約多項式は(x²-1)=(x+1)(x-1)と分かった。
実際、2x⁹-x⁸-2x+1=(x⁴+1)(x²+1)(2x-1)(x+1)(x-1)、x⁴+x³-x-1=(x+1)(x-1)(x²+x+1)であることから確認できる。
先ほどの表と対応させると以下のようになる。

	m	n	r
(1)	2x9-x8-2x+1	x4+x3-x-1	2x3-x2-2x+1
(2)	x4+x3-x-1	2x3-x2-2x+1	x2-1
(3)	2x3-x2-2x+1	x2-1	0
(4)	x2-1	0	-

一般に、ユークリッド整域と呼ばれる集合であればユークリッドの互除法が使える。整数の集合と1変数の多項式の集合は共にユークリッド整域の構造を持つ。しかし、2変数以上の多項式はユークリッド整域ではないのでユークリッドの互除法を適用する事ができない。直接因数分解するより余計めんどくさいが1変数多項式に互除法を適用できるという事実が重要なのである。用語の詳しい説明は環(数学)を参照。

こちらも拡張ユークリッドの互除法が使えるが、係数が多く非常にめんどくさいことになる。

関連動画

高校数学の範囲での証明方法である。

関連項目

• アルゴリズム
• プログラミング関連用語の一覧
• 数学関連用語の一覧
• 環(数学)