ユークリッドの互除法
出典: フリー百科事典『ウィキペディア（Wikipedia）』
ユークリッドの互除法（-ごじょほう）は、2つの自然数または整式の最大公約数を求める手法の一つである。2つの自然数（または整式）a、bについて、aのbによる剰余をrとすると、aとbとの最大公約数はbとrとの最大公約数に等しいが、この性質に基き、bのrによる剰余を求め、rをさらにbのrによる剰余で割った剰余を求め、と同様の手続きを繰り返すと、剰余が0になった時の除数がすなわちaとbとの最大公約数である、というもの。明示的に記述された最古のアルゴリズムとしても知られ、紀元前300年頃に記されたユークリッドの『原論』第7巻、命題1から3がそれである。
目次 |
[編集] 例
(問題)1071と1029の最大公約数を求める。
- 1071は1029では割り切れないので、1071を1029で割った余りを求める。=> 42
- 1029は42では割り切れないので、1029を42で割った余りを求める。=>21
- 42は21で割り切れる。
よって、最大公約数は21である。
[編集] アルゴリズム
- 入力をm,nとする。
- nが0なら、mを出力してアルゴリズムを終了する。
- nがmを割り切るなら、nを出力してアルゴリズムを終了する。
- そうでないなら、mをnで割った余りを新たにmとし、更にmとnを取り替えて3に戻る。
上記の手順は「n,mに対して剰余の演算を行うことができる」という仮定だけに依っているので、整数環だけではなく任意のユークリッド整域においても同様にして最大公約因子を求めることができる。
[編集] 拡張された互除法
整数 m, n の最大公約数 (Greatest Common Divisor) を gcd(m,n) と表すときに、（拡張された）ユークリッドの互除法を用いて、am + bn = gcd(m,n) の解となる整数 a, b の組を見つけることができる。上の場合、
- 1071 = 1 * 1029 + 42
- 1029 = 24 * 42 + 21
- 42 = 2 * 21
であるから、
- 21 = 1029 - 24 * 42 = 1029 - 24 * (1071 - 1 * 1029)
- = -24 * 1071 + 25 * 1029
となる。
特に、m, n が互いに素（最大公約数が 1）である場合、am + bn = c は任意の整数 c に対して整数解 (a,b) をもつことが分かる。
[編集] 計算量
割って余りを取るという操作を、最悪でも小さい方の十進法での桁数の5倍繰り返せば、最大公約数に達する。（ラメの定理）
最大公約数を求めるのに、素因数分解してみればいいと考える人がいるかもしれないが、この定理は素因数分解を用いるよりもユークリッドの互除法による方がはるかに速いということを言っている。
実際、計算複雑性理論に於いては最大公約数を求めることは「容易な問題」として知られており、素因数分解は「困難な問題」であろうと考えられている。 入力された２つの整数のビット数をnとすれば、ユークリッドアルゴリズムは Θ(n) 回の除算で最大公約数を求められる。
[編集] 連分数
上の例で出てきた、1071と1029の最大公約数を求める過程は、次のように表せる。
すなわち、
したがって、
このように、nとm(n>m)の最大公約数を求める際のユークリッドの互除法の割り算の商は、有理数n/mの連分数展開になっている。
