ユークリッドの互除法

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動先: 案内検索
252と105のためのユークリッドの互除法のアニメーション。
クロスバーは、最大公約数(GCD)である21の倍数を表す。
それぞれのステップにおいて、1つの番号がゼロになるまで、より少ない数はより大きな数から引かれる。
残りの数は、GCD。

ユークリッドの互除法(ユークリッドのごじょほう、: Euclidean Algorithm)は、2 つの自然数または整式の最大公約数を求める手法の一つである。

2 つの自然数(または整式) a, b (ab) について、ab による剰余を r とすると、 ab との最大公約数は br との最大公約数に等しいという性質が成り立つ。この性質を利用して、 br で割った剰余、 除数 r をその剰余で割った剰余、と剰余を求める計算を逐次繰り返すと、剰余が 0 になった時の除数が ab との最大公約数となる。

明示的に記述された最古のアルゴリズムとしても知られ、紀元前300年頃に記されたユークリッドの『原論』第 7 巻、命題 1 から 3 がそれである[注釈 1]

[編集]

(問題) 1071 と 1029 の最大公約数を求める。

  • 1071 を 1029 で割った余りは 42
  • 1029 を 42 で割った余りは 21
  • 42 を 21 で割った余りは 0

よって、最大公約数は21である。

証明[編集]

a, b は自然数で a ≠ 0 とする。 ba で割った商を q、剰余を r とすると

b = qa + r

今、d0ar の両方を割り切る自然数とする。

このとき d0 は積 qa を割り切るから、和 qa + r も割り切るが、qa + rb に等しい。したがって、d0ab を割り切る。すなわち ar の公約数はすべてbaの公約数である。

逆に、d1ba の両方を割り切る自然数とする。

d1qa を割り切るから差 b - qa を割り切るが、b - qar に等しい。したがって、d1arを割り切る。言い換えると ba の公約数はすべてar の公約数である。

したがって、ba の公約数全体の集合は ar の公約数全体の集合に等しく、特に ba の最大公約数は ar の最大公約数でなければならない。

アルゴリズム[編集]

ユークリッドの互除法の仕組みは、この図のように最大公約数を求める対象の2つの整数を幅と高さに設定した長方形内での赤色の斜めの直線の描画過程によっても表現できる。 赤色の斜めの直線の描画は、はじめはその長方形内を描画範囲とし、その角から内部に向け、かつ、その辺に対して45度の差を持たせて開始する。 描画範囲の辺の途中に当たれば、その内部へ直角反射するように角度を変える。 赤色の斜めの直線が反射後に描画範囲の向かいの辺と異なる辺の途中に当たる場合、描画範囲の長辺の長さを短辺の長さで割ると余りが生じる状態となっており、直前の反射地点を足掛かりに描画範囲を垂直に区切ってその範囲を絞りこむ。 (区切られて出来た小さいほうの範囲を以後の描画範囲とする) (除数および被除数の変更に相当) 赤色の斜めの直線が描画範囲の角に到達した場合、描画範囲の長辺の長さを短辺の長さで余りなく割れる状態となっており、描画の終了となり、最後にして最小の描画範囲(桃色の範囲)の短辺の長さが最大公約数となる。
  1. 入力を m, n (mn) とする。
  2. n = 0 なら、 m を出力してアルゴリズムを終了する。
  3. mn で割った余りを新たに n とし、更に 元のnを新たにm とし 2. に戻る。

上記の手順は「n, m に対して剰余の演算を行うことができる」という仮定だけに依っているので、整数環だけではなく任意のユークリッド整域においても同様にして最大公約因子を求めることができる。

拡張された互除法[編集]

整数 m, n の最大公約数 (: Greatest Common Divisor) を gcd(m,n) と表すときに、(拡張された)ユークリッドの互除法を用いて、mx + ny = gcd(m, n) の解となる整数 x, y の組を見つけることができる。上の例の場合、m = 1071, n = 1029 のとき、

1071 = 1 × 1029 + 42
1029 = 24 × 42 + 21
42 = 2 × 21

であるから、gcd(1071, 1029) = 21 であり、

21 = 1029 − 24 × 42 
= 1029 − 24 × (1071 − 1 × 1029)
= −24 × 1071 + 25 × 1029

となるので、x = −24, y = 25 である。

特に、m, n互いに素(最大公約数が 1)である場合、mx + ny = 1 の整数解を (x, y) とすると、mx + ny = c は任意の整数 c に対して整数解 (cx, cy) をもつことが分かる。

一般に、 において、ユークリッドの互除法の各過程を繰り返して

が得られるとき、

すなわち

ここで

とおくと、 であるからは存在して

これらの過程において、、ユークリッドの互除法により、であるから、を考慮すると、

となる。

とおき、ユークリッドの互除法の各過程で得られた , , 等を用いて、右辺を計算すれば、左辺の, が求まり、これはベズーの等式

を満たす[6]

計算量[編集]

割って余りを取るという操作を、最悪でも小さい方の十進法での桁数の約 5 倍繰り返せば、最大公約数に達する(ラメの定理)。

最大公約数を求めるのに、素因数分解してみればいいと考える人がいるかもしれないが、この定理は素因数分解を用いるよりもユークリッドの互除法による方がはるかに速いということを述べている。

実際、計算複雑性理論においては最大公約数を求めることは「容易な問題」として知られており、素因数分解は「困難な問題」であろうと考えられている。 入力された2つの整数のうち小さいほうの整数 n の桁数を d とすれば、ユークリッドの互除法では O(d) 回の除算で最大公約数が求められる。桁数 d は O(log n) なので、ユークリッドの互除法では O(log n) 回の除算で最大公約数が求められる。

連分数[編集]

上の例で出てきた、1071 と 1029 の最大公約数を求める過程は、次のように表せる。

すなわち、

したがって、

このように、 nm (n > m) の最大公約数を求める際のユークリッドの互除法の割り算の商は、有理数 n/m連分数展開になっている。

脚注[編集]

[ヘルプ]

注釈[編集]

  1. ^ 原論』第7巻では、1を単位と定義し、2以上の自然数をと定義している[1]
    定義
    1. 単位とは存在するもののおのおのがそれによって 1 とよばれるものである。
    2. 数とは単位から成る多である。
    ユークリッドの互除法は以下の命題 1 から 3 において述べられている。
    命題
    1. 二つの不等な数が定められ、常に大きい数から小さい数が引き去られるとき、もし単位が残されるまで、残された数が自分の前の数を割り切らないならば、最初の 2 数は互いに素であろう[2]
    2. 互いに素でない 2 数が与えられたとき、それらの最大公約数を見いだすこと[3]
      1. これから次のことが明らかである。すなわちもしある数が二つの数を割り切るならば、それらの最大公約数をも割り切るであろう。これが証明すべきことであった[4]
    3. 互いに素でない三つの数が与えられたとき、それらの最大公約数を見いだすこと[5]

出典[編集]

参考文献[編集]

関連項目[編集]

外部リンク[編集]