ユークリッドの互除法
出典: フリー百科事典『ウィキペディア（Wikipedia）』
ユークリッドの互除法（-ごじょほう）は、2 つの自然数または整式の最大公約数を求める手法の一つである。
2 つの自然数（または整式） a, b (a ≧ b) について、a の b による剰余を r とすると、 a と b との最大公約数は b と r との最大公約数に等しいという性質が成り立つ。この性質を利用して、 b を r で割った剰余、 除数 r をその剰余で割った剰余、と剰余を求める計算を逐次繰り返すと、剰余が 0 になった時の除数が a と b との最大公約数となる。
明示的に記述された最古のアルゴリズムとしても知られ、紀元前300年頃に記されたユークリッドの『原論』第 7 巻、命題 1 から 3 がそれである。
目次 |
[編集] 例
(問題) 1071 と 1029 の最大公約数を求める。
- 1071 を 1029 で割った余りは 42
- 1029 を 42 で割った余りは 21
- 42 を 21 で割った余りは 0
よって、最大公約数は21である。
[編集] アルゴリズム
- 入力を m, n (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 とすれば、ユークリッドアルゴリズムは O(n) 回の除算で最大公約数を求められる。
[編集] 連分数
上の例で出てきた、1071 と 1029 の最大公約数を求める過程は、次のように表せる。
すなわち、
したがって、
このように、 n と m (n > m) の最大公約数を求める際のユークリッドの互除法の割り算の商は、有理数 n/m の連分数展開になっている。
