ユークリッドの互除法
ユークリッドの互除法（ユークリッドのごじょほう）は、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である。
証明
<math>a, b</math> は自然数で <math>a</math> ≠ <math>0</math> とする。 <math>b</math> を <math>a</math> で割った商を <math>q</math>、剰余を <math>r</math> とすると
- <math>b = qa + r </math>
今、<math>d</math> を <math>a</math> と <math>r</math> の両方を割り切る自然数とする。
このとき <math>d</math> は積<math>qa</math>を割り切るから、和<math>qa+r</math>も割り切るが、
<math>qa+r</math> は <math>b</math>である。したがって、<math>d</math> は <math>a</math> と
<math>b</math> を割り切る。すなわち <math>a</math> と <math>r</math> の公約数はすべて
<math>b</math> と <math>a</math>の公約数である。
逆に、<math>d'</math> を <math>b</math> と <math>a</math> の両方を割り切る自然数とする。
<math>d'</math> は <math>qa</math> を割り切るから差 <math>b-qa</math> を割り切るが、
<math>b-qa</math> は <math>r</math> に等しい。したがって、<math>d'</math> は <math>a</math> と
<math>r</math>を割り切る。言い換えると <math>b</math> と <math>a</math> の公約数はすべて
<math>a</math> と <math>r</math> の公約数である。
したがって、<math>b</math> と <math>a</math> の公約数全体の集合は <math>a</math> と <math>r</math>
の公約数全体の集合に等しく、特に <math>b</math> と <math>a</math> の最大公約数は <math>a</math> と <math>r</math> の最大公約数でなければならない。
アルゴリズム
- 入力を m, n (m ≧ n) とする。
- n = 0 なら、 m を出力してアルゴリズムを終了する。
- m を n で割った余りを新たに n とし、更に 元のnを新たにm とし 2. に戻る。
上記の手順は「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) をもつことが分かる。
一般に、<math> m = r_{0}, n = r_{1} </math> において、ユークリッドの互除法の各過程を繰り返して
- <math>r_{0} = k_{0}r_{1} + r_{2} ( 0 < r_{2} < r_{1})</math>
- <math>r_{1} = k_{1}r_{2} + r_{3} ( 0 < r_{3} < r_{2})</math>
- <math>r_{2} = k_{2}r_{3} + r_{4} ( 0 < r_{4} < r_{3})</math>
- <math>...</math>
- <math>r_{h - 1} = k_{h - 1}r_{h} + 0</math>
が得られるとき、
- <math>
\begin{pmatrix} r_{0} \\ r_{1} \\ \end{pmatrix} = \begin{pmatrix} k_{0} & 1 \\ 1 & 0 \\ \end{pmatrix} \begin{pmatrix} r_{1} \\ r_{2} \\ \end{pmatrix}</math>
- <math>
\begin{pmatrix} r_{1} \\ r_{2} \\ \end{pmatrix} = \begin{pmatrix} k_{1} & 1 \\ 1 & 0 \\ \end{pmatrix} \begin{pmatrix} r_{2} \\ r_{3} \\ \end{pmatrix}</math>
- <math>
\begin{pmatrix} r_{2} \\ r_{3} \\ \end{pmatrix} = \begin{pmatrix} k_{2} & 1 \\ 1 & 0 \\ \end{pmatrix} \begin{pmatrix} r_{3} \\ r_{4} \\ \end{pmatrix}</math>
- <math>...</math>
- <math>
\begin{pmatrix} r_{h-1} \\ r_{h} \\ \end{pmatrix} = \begin{pmatrix} k_{h - 1} & 1 \\ 1 & 0 \\ \end{pmatrix} \begin{pmatrix} r_{h} \\ 0 \\ \end{pmatrix}</math> すなわち
- <math>
\begin{pmatrix} r_{0} \\ r_{1} \\ \end{pmatrix} = \begin{pmatrix} k_{0} & 1 \\ 1 & 0 \\ \end{pmatrix} \begin{pmatrix} k_{1} & 1 \\ 1 & 0 \\ \end{pmatrix} \begin{pmatrix} k_{2} & 1 \\ 1 & 0 \\ \end{pmatrix} \begin{pmatrix} k_{3} & 1 \\ 1 & 0 \\ \end{pmatrix} ... \begin{pmatrix} k_{h-1} & 1 \\ 1 & 0 \\ \end{pmatrix} \begin{pmatrix} r_{h} \\ 0 \\ \end{pmatrix}</math> ここで
- <math>
K_{i}= \begin{pmatrix} k_{i} & 1 \\ 1 & 0 \\ \end{pmatrix}</math> とおくと、<math>|K_{i}|=-1</math> であるから<math>K_{i}^{-1}</math>は存在して
- <math>
\begin{pmatrix} k_{h-1} & 1 \\ 1 & 0 \\ \end{pmatrix}^{-1} \begin{pmatrix} k_{h-2} & 1 \\ 1 & 0 \\ \end{pmatrix}^{-1} ... \begin{pmatrix} k_{2} & 1 \\ 1 & 0 \\ \end{pmatrix}^{-1} \begin{pmatrix} k_{1} & 1 \\ 1 & 0 \\ \end{pmatrix}^{-1} \begin{pmatrix} k_{0} & 1 \\ 1 & 0 \\ \end{pmatrix}^{-1} \begin{pmatrix} r_{0} \\ r_{1} \\ \end{pmatrix} = \begin{pmatrix} r_{h} \\ 0 \\ \end{pmatrix} </math> これらの過程において、<math>m = r_{0}, n = r_{1} </math>、ユークリッドの互除法により、<math>r_{h}=gcd(m, n)</math>であるから、<math>K_{i}^{-1}=\begin{pmatrix} 0 & 1 \\ 1 & -k_{i} \\ \end{pmatrix}</math>を考慮すると、
- <math>
\begin{pmatrix} 0 & 1 \\ 1 & -k_{h - 1} \\ \end{pmatrix} \begin{pmatrix} 0 & 1 \\ 1 & -k_{h - 2} \\ \end{pmatrix} ... \begin{pmatrix} 0 & 1 \\ 1 & -k_{2} \\ \end{pmatrix} \begin{pmatrix} 0 & 1 \\ 1 & -k_{1} \\ \end{pmatrix} \begin{pmatrix} 0 & 1 \\ 1 & -k_{0} \\ \end{pmatrix} \begin{pmatrix} m \\ n \\ \end{pmatrix} = \begin{pmatrix} gcd(m, n) \\ 0 \\ \end{pmatrix}</math> となる。
- <math>
\begin{pmatrix} a & b \\ u & v \\ \end{pmatrix} = \begin{pmatrix} 0 & 1 \\ 1 & -k_{h - 1} \\ \end{pmatrix} \begin{pmatrix} 0 & 1 \\ 1 & -k_{h - 2} \\ \end{pmatrix} ... \begin{pmatrix} 0 & 1 \\ 1 & -k_{2} \\ \end{pmatrix} \begin{pmatrix} 0 & 1 \\ 1 & -k_{1} \\ \end{pmatrix} \begin{pmatrix} 0 & 1 \\ 1 & -k_{0} \\ \end{pmatrix}</math> とおき、ユークリッドの互除法の各過程で得られた <math>k_{0}</math>, <math>k_{1}</math>, <math>k_{2}</math>等を用いて、右辺を計算すれば、左辺の<math>a</math>, <math>b</math> が求まり、これは
- <math>am+bn=gcd(m,n)</math>
を満たす。[1] テンプレート:Reflist
計算量
割って余りを取るという操作を、最悪でも小さい方の十進法での桁数の約 5 倍繰り返せば、最大公約数に達する（ラメの定理）。
最大公約数を求めるのに、素因数分解してみればいいと考える人がいるかもしれないが、この定理は素因数分解を用いるよりもユークリッドの互除法による方がはるかに速いということを述べている。
実際、計算複雑性理論に於いては最大公約数を求めることは「容易な問題」として知られており、素因数分解は「困難な問題」であろうと考えられている。 入力された2つの整数のうち小さいほうの整数 n の桁数を d とすれば、ユークリッドの互除法では O(d) 回の除算で最大公約数が求められる。桁数 d は O(log n) なので、ユークリッドの互除法では O(log n) 回の除算で最大公約数が求められる。
連分数
上の例で出てきた、1071 と 1029 の最大公約数を求める過程は、次のように表せる。
- <math>\begin{align}
1071 &= 1029 \times 1 + 42, \\ 1029 &= 42 \times 24 + 21, \\ 42 &= 21 \times 2. \end{align}</math> すなわち、
- <math>\begin{align}
\frac{1071}{1029} &= 1 + \frac{42}{1029}, \\ \frac{1029}{42} &= 24 + \frac{21}{42}, \\ \frac{42}{21} &= 2. \end{align}</math> したがって、
- <math>\frac{1071}{1029} = 1 + \frac{1}{24 + \frac{1}{2}}</math>
このように、 n と m (n > m) の最大公約数を求める際のユークリッドの互除法の割り算の商は、有理数 n/m の連分数展開になっている。
テンプレート:Link GA- ↑ 例えば「2次行列の世界」,岩堀 長慶,岩波書店(1983)
