ニコニコ大百科モバイル

7/2(月)よりスマホまたはPCでアクセスした場合、各デバイス向けのサイトへ自動で転送致します


ユークリッドの互除法


ヨミ: ユークリッドノゴジョホウ
掲示板をミル!
11カキコ!

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


概要


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

  1. n = 0の場合、m を最大公約数として終了する。n ≠ 0(すなわち n > 0)の場合、2.へ進む。
  2. m ÷ n剰余r とする。
  3. mnnr を代入する。
  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 であるため、mn の大小関係に関して特に制約はい。


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


ここではC言語での実装例を記載する。他のプログラミング言語においても、ループ処理、再帰処理等が実装であれば大体同じようにして実装出来る。なお、引数 mn については前提条件(どちらか一方が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-69320-693=7220-693×21

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

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

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

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

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


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


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

例 2x9-x8-2x+1 と x4+x3-x-1 の最大公約多項式を実数係数の範囲でめる。

(2x9-x8-2x-1)=(x4+x3-x-1)(2x5-3x4+3x3-x2)+(2x3-x2-2x+1)

(x4+x3-x-1)=(2x3-x2-2x+1)(x/2+3/4)+7/4(x2-1)

(2x3-x2-2x+1)=7/4(x2-1)(8x/7-4/7)+0=(x2-1)(2x-1)+0

大公約多項式は(x2-1)=(x+1)(x-1)と分かった。
実際、2x9-x8-2x+1=(x4+1)(x2+1)(2x-1)(x+1)(x-1)、x4+x3-x-1=(x+1)(x-1)(x2+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変数多項式に互除法を適用できるという事実が重要なのである。用の詳しい説明は環(数学)を参照。

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


関連動画



■sm18276493[ニコ動]

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


関連項目



最終更新日: 18/07/31 04:22
タグ検索 パソコン版を見る


[0]TOP
ニコニコ動画モバイル
運営元:ドワンゴ