|
|
| 1行目: |
1行目: |
| − | [[File:Euclidean algorithm 252 105 animation flipped.gif|thumb|upright|
| + | '''ユークリッドの互除法'''（ユークリッドのごじょほう、{{Lang-en-short|Euclidean Algorithm}}） |
| − | 252と105のためのユークリッドの互除法のアニメーション。<br />
| |
| − | クロスバーは、最大公約数（GCD）である21の倍数を表す。 <br />
| |
| − | それぞれのステップにおいて、1つの番号がゼロになるまで、より少ない数はより大きな数から引かれる。 <br />
| |
| − | 残りの数は、GCD。<br />]]
| |
| | | | |
| − | '''ユークリッドの互除法'''（ユークリッドのごじょほう、{{Lang-en-short|Euclidean Algorithm}}）は、2 つの[[自然数]]の[[最大公約数]]を求める手法の一つである。
| + | 二つの[[自然数]]<html> |
| | + | <i>a</i> |
| | + | <sub>1</sub>と <i>a</i> |
| | + | <sub>2</sub>の最大公約数（[[約数]]）を求めるための一つの方法。<i>a</i> |
| | + | <sub>1</sub>≧<i>a</i> |
| | + | <sub>2</sub>として，次の割り算を実行する。 |
| | | | |
| − | 2 つの自然数 ''a'', ''b'' (''a'' ≧ ''b'') について、''a'' の ''b'' による剰余を ''r'' とすると、 ''a'' と ''b'' との最大公約数は ''b'' と ''r'' との最大公約数に等しいという性質が成り立つ。この性質を利用して、 ''b'' を ''r'' で割った剰余、 除数 ''r'' をその剰余で割った剰余、と剰余を求める計算を逐次繰り返すと、剰余が 0 になった時の除数が ''a'' と ''b'' との最大公約数となる。
| + | |
| − | | + | <table border="0" cellspacing="10" width="559"> |
| − | 明示的に記述された最古の[[アルゴリズム]]としても知られ、紀元前300年頃に記された[[エウクレイデス|ユークリッド]]の『[[ユークリッド原論|原論]]』第 7 巻、命題 1 から 3 がそれである{{refnest|group=注釈|『原論』第7巻では、1 を'''単位'''と定義し、2 以上の自然数を'''数'''と定義している{{sfn|ユークリッド|中村ほか|1996|p=149}}。
| + | |
| − | ;定義
| + | <tbody><tr> |
| − | #単位とは存在するもののおのおのがそれによって 1 とよばれるものである。
| + | |
| − | #数とは単位から成る多である。
| + | <td> |
| − | ユークリッドの互除法は以下の命題 1 から 3 において述べられている。
| + | <i>a</i> |
| − | ;命題
| + | <sub>1</sub>＝<i>a</i> |
| − | #二つの不等な数が定められ、常に大きい数から小さい数が引き去られるとき、もし単位が残されるまで、残された数が自分の前の数を割り切らないならば、最初の 2 数は互いに素であろう{{sfn|ユークリッド|中村ほか|1996|pp=150f}}。
| + | <sub>2</sub> |
| − | #互いに素でない 2 数が与えられたとき、それらの最大公約数を見いだすこと{{sfn|ユークリッド|中村ほか|1996|p=151}}。
| + | <i>q</i> |
| − | ##これから次のことが明らかである。すなわちもしある数が二つの数を割り切るならば、それらの最大公約数をも割り切るであろう。これが証明すべきことであった{{sfn|ユークリッド|中村ほか|1996|p=152}}。
| + | <sub>1</sub>＋<i>a</i> |
| − | #互いに素でない三つの数が与えられたとき、それらの最大公約数を見いだすこと{{sfn|ユークリッド|中村ほか|1996|pp=152f}}。}}。
| + | <sub>3</sub> |
| − | | + | |
| − | == 例 ==
| + | </td> |
| − | (問題) 1071 と 1029 の最大公約数を求める。
| + | |
| − | *1071 を 1029 で割った余りは 42
| + | <td> </td> |
| − | *1029 を 42 で割った余りは 21
| + | |
| − | *42 を 21 で割った余りは 0
| + | <td> |
| − | よって、最大公約数は21である。
| + | <i>q</i> |
| − | | + | <sub>1</sub>は商，<i>a</i> |
| − | == 証明 ==
| + | <sub>3</sub>は余り |
| − | ''a'', ''b'' は自然数で ''a'' ≠ 0 とする。
| + | </td> |
| − | ''b'' を ''a'' で割った商を ''q''、剰余を ''r'' とすると
| + | |
| − | :''b'' = ''qa'' + ''r''
| + | </tr> |
| − | 今、''d<sub>0</sub>'' を ''a'' と ''r'' の両方を割り切る自然数とする。
| + | |
| − | | + | <tr> |
| − | このとき ''d<sub>0</sub>'' は積 ''qa'' を割り切るから、和 ''qa'' + ''r'' も割り切るが、''qa'' + ''r'' は ''b'' に等しい。したがって、''d<sub>0</sub>'' は ''a'' と''b'' を割り切る。すなわち ''a'' と ''r'' の公約数はすべて''b'' と ''a''の公約数である。
| + | |
| − | | + | <td> |
| − | 逆に、''d<sub>1</sub>'' を ''b'' と ''a'' の両方を割り切る自然数とする。
| + | <i>a</i> |
| − | | + | <sub>2</sub>＝<i>a</i> |
| − | ''d<sub>1</sub>'' は ''qa'' を割り切るから差 ''b'' - ''qa'' を割り切るが、''b'' - ''qa'' は ''r'' に等しい。したがって、''d<sub>1</sub>'' は ''a'' と''r''を割り切る。言い換えると ''b'' と ''a'' の公約数はすべて''a'' と ''r'' の公約数である。
| + | <sub>3</sub> |
| − | | + | <i>q</i> |
| − | したがって、''b'' と ''a'' の公約数全体の集合は ''a'' と ''r'' の公約数全体の集合に等しく、特に ''b'' と ''a'' の最大公約数は ''a'' と ''r'' の最大公約数でなければならない。
| + | <sub>2</sub>＋<i>a</i> |
| − | | + | <sub>4</sub> |
| − | == 手続き的記述 ==
| + | |
| − | [[File:GCM_Of_20_And_32.gif|thumb|right|480px|
| + | </td> |
| − | ユークリッドの互除法の仕組みは、この図のように最大公約数を求める対象の２つの整数を幅と高さに設定した長方形内での赤色の斜めの直線の描画過程によっても表現できる。
| + | |
| − | 赤色の斜めの直線の描画は、はじめはその長方形内を描画範囲とし、その角から内部に向け、かつ、その辺に対して45度の差を持たせて開始する。
| + | <td> </td> |
| − | 描画範囲の辺の途中に当たれば、その内部へ直角反射するように角度を変える。
| + | |
| − | 赤色の斜めの直線が反射後に描画範囲の向かいの辺と異なる辺の途中に当たる場合、描画範囲の長辺の長さを短辺の長さで割ると余りが生じる状態となっており、直前の反射地点を足掛かりに描画範囲を垂直に区切ってその範囲を絞りこむ。
| + | <td> |
| − | （区切られて出来た小さいほうの範囲を以後の描画範囲とする）
| + | <i>q</i> |
| − | （除数および被除数の変更に相当）
| + | <sub>2</sub>は商，<i>a</i> |
| − | 赤色の斜めの直線が描画範囲の角に到達した場合、描画範囲の長辺の長さを短辺の長さで余りなく割れる状態となっており、描画の終了となり、最後にして最小の描画範囲の短辺の長さが最大公約数となる。]]
| + | <sub>4</sub>は余り |
| − | 手続き的に記述すると、次のようになる。
| + | </td> |
| − | # 入力を ''m'', ''n'' (''m'' ≧ ''n'') とする。
| + | |
| − | # ''n'' = 0 なら、 ''m'' を出力して[[アルゴリズム]]を終了する。
| + | </tr> |
| − | # ''m'' を ''n'' で割った余りを新たに ''n'' とし、更に 元の''n''を新たに''m'' とし 2. に戻る。
| + | |
| − | | + | <tr> |
| − | 上記の手順は「''n'', ''m'' に対して剰余の演算を行うことができる」という仮定だけに依っているので、[[整数環]]だけではなく任意の[[ユークリッド整域]]においても同様にして最大公約因子を求めることができる。
| + | |
| − | | + | <td align="center">…………</td> |
| − | == 拡張された互除法 ==
| + | |
| − | 整数 ''m'', ''n'' の最大公約数 ({{Lang-en-short|Greatest Common Divisor}}) を gcd(''m'',''n'') と表すときに、（拡張された）ユークリッドの互除法を用いて、''mx'' + ''ny'' = gcd(''m'', ''n'') の解となる整数 ''x'', ''y'' の組を見つけることができる。[[#例|上の例]]の場合、''m'' = 1071, ''n'' = 1029 のとき、
| + | <td> </td> |
| − | :1071 = 1 × 1029 + 42
| + | |
| − | :1029 = 24 × 42 + 21
| + | <td align="center">…………</td> |
| − | :42 = 2 × 21
| + | |
| − | であるから、gcd(1071, 1029) = 21 であり、
| + | </tr> |
| − | :21 = 1029 − 24 × 42
| + | |
| − | := 1029 − 24 × (1071 − 1 × 1029)
| + | <tr> |
| − | := −24 × 1071 + 25 × 1029
| + | |
| − | となるので、''x'' = −24, ''y'' = 25 である。
| + | <td> |
| − | | + | <i>a<sub>n</sub> |
| − | 特に、''m'', ''n'' が[[互いに素]]（最大公約数が 1）である場合、''mx'' + ''ny'' = 1 の整数解を (''x'', ''y'') とすると、''mx'' + ''ny'' = ''c'' は任意の整数 ''c'' に対して整数解 (''cx'', ''cy'') をもつことが分かる。
| + | </i> |
| − | | + | <sub>-1</sub>＝<i>a</i> |
| − | | + | <sub>n</sub> |
| − | 一般に、<math>
| + | <i>q<sub>n</sub> |
| − | m = r_{0}, n = r_{1} </math>
| + | </i> |
| − | において、ユークリッドの互除法の各過程を繰り返して
| + | <sub>-1</sub>＋<i>a<sub>n</sub> |
| − | :<math>r_{0} = k_{0}r_{1} + r_{2} \ \ ( 0 < r_{2} < r_{1})</math>
| + | </i> |
| − | :<math>r_{1} = k_{1}r_{2} + r_{3} \ \ ( 0 < r_{3} < r_{2})</math>
| + | <sub>+1</sub> |
| − | :<math>r_{2} = k_{2}r_{3} + r_{4} \ \ ( 0 < r_{4} < r_{3})</math>
| + | |
| − | :<math>...</math>
| + | </td> |
| − | :<math>r_{h - 1} = k_{h - 1}r_{h} + 0</math>
| + | |
| − | が得られるとき、
| + | <td> </td> |
| − | :<math>
| + | |
| − | \begin{pmatrix}
| + | <td> |
| − | r_{0} \\
| + | <i>q</i> |
| − | r_{1} \\
| + | <sub>n</sub> |
| − | \end{pmatrix}
| + | <sub>-1</sub>は商，<i>a</i> |
| − | =
| + | <sub>n</sub> |
| − | \begin{pmatrix}
| + | <sub>+1</sub>は余り |
| − | k_{0} & 1 \\
| + | </td> |
| − | 1 & 0 \\
| + | |
| − | \end{pmatrix}
| + | </tr> |
| − | \begin{pmatrix}
| + | |
| − | r_{1} \\
| + | <tr> |
| − | r_{2} \\
| + | |
| − | \end{pmatrix}</math>
| + | <td> |
| − | :<math>
| + | <i>a</i> |
| − | \begin{pmatrix}
| + | <sub>n</sub>＝<i>a</i> |
| − | r_{1} \\
| + | <sub>n＋1</sub> |
| − | r_{2} \\
| + | <i>q</i> |
| − | \end{pmatrix}
| + | <sub>n</sub> |
| − | =
| + | |
| − | \begin{pmatrix}
| + | </td> |
| − | k_{1} & 1 \\
| + | |
| − | 1 & 0 \\
| + | <td> </td> |
| − | \end{pmatrix}
| + | |
| − | \begin{pmatrix}
| + | <td> |
| − | r_{2} \\
| + | <i>q</i> |
| − | r_{3} \\
| + | <sub>n</sub>は商，余りはなし |
| − | \end{pmatrix}</math>
| + | </td> |
| − | :<math>
| + | |
| − | \begin{pmatrix}
| + | </tr> |
| − | r_{2} \\
| + | |
| − | r_{3} \\
| + | </tbody></table> |
| − | \end{pmatrix}
| + | |
| − | =
| + | 最後に余りがなかったならば，この <i>a<sub>n</sub> |
| − | \begin{pmatrix}
| + | </i> |
| − | k_{2} & 1 \\
| + | <sub>+1</sub>が最初の 2数 <i>a</i> |
| − | 1 & 0 \\
| + | <sub>1</sub>と <i>a</i> |
| − | \end{pmatrix}
| + | <sub>2</sub></html>の最大公約数である。（[[整数論]]，[[ユークリッド]]） |
| − | \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}
| |
| − | x & y \\
| |
| − | 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>x</math>, <math>y</math> が求まり、これは[[ベズーの等式]]
| |
| − | :<math>mx+ny=\gcd(m,n)</math>
| |
| − | を満たす{{sfn|岩堀|1983}}。
| |
| − | | |
| − | == 計算量 ==
| |
| − | 割って余りを取るという操作を、最悪でも小さい方の十進法での桁数の約 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'' の[[連分数展開]]になっている。
| |
| − | | |
| − | == 脚注 ==
| |
| − | {{脚注ヘルプ}}
| |
| − | === 注釈 ===
| |
| − | {{reflist|group="注釈"}}
| |
| − | === 出典 ===
| |
| − | {{Reflist|2}}
| |
| − | | |
| − | == 参考文献 ==
| |
| − | *{{Cite book|和書|author=[[岩堀長慶]]|date=1983-04-22|title=2次行列の世界|series=数学入門シリーズ 4|publisher=[[岩波書店]]|isbn=4-00-007634-5|url=http://www.iwanami.co.jp/.BOOKS/00/5/0076340.html|ref={{Harvid|岩堀|1983}}}}
| |
| − | *{{Cite book|和書|editor=[[ヨハン・ルードウィッヒ・ハイベア|ハイベア]]・[[ハインリッヒ・メンゲ|メンゲ]]編|others=[[中村幸四郎]]・[[寺阪英孝]]・[[伊東俊太郎]]・[[池田美恵]]訳・解説|title=ユークリッド原論|publisher=[[共立出版]]|ref={{Harvid|ユークリッド|中村ほか|1996}}}} - 全13巻の最初の邦訳。
| |
| − | ** （ハードカバー）1971年7月。ISBN 4-320-01072-8
| |
| − | ***（抜粋）『[[世界の名著]]9』 池田美恵訳 [[中央公論社]] 1972年
| |
| − | ** （縮刷版）1996年6月。ISBN 4-320-01513-4
| |
| − | ** （[http://www.kyoritsu-pub.co.jp/bookdetail/9784320019652 追補版]）2011年5月。ISBN 978-4-320-01965-2
| |
| − | *{{Cite book|和書|editor=[[ヨハン・ルードウィッヒ・ハイベア|ハイベア]]・[[ハインリッヒ・メンゲ|メンゲ]]編|title=エウクレイデス全集|volume=（全5巻）|publisher=[[東京大学出版会]]|url=http://www.utp.or.jp/series/eucleides.html|ref=東大版}} - 「エウクレイデス全集」の世界初の近代語訳。
| |
| − | ** 第2巻 [http://www.utp.or.jp/bd/978-4-13-065302-2.html 原論VII－X]、[[斎藤憲]] 訳・解説、2015年8月。ISBN 978-4-13-065302-2
| |
| − | | |
| − | == 関連項目 ==
| |
| − | {{Div col}}
| |
| − | *[[ベズーの等式]]
| |
| − | *[[ユークリッド環]]
| |
| − | {{Div col end}}
| |
| − | | |
| − | == 外部リンク ==
| |
| − | *{{Kotobank|ユークリッドの互除法|2=日本大百科全書(ニッポニカ)}}
| |
| − | *{{MathWorld|title=Euclidean Algorithm|urlname=EuclideanAlgorithm}}
| |
| − | *{{SpringerEOM|title=Euclidean algorithm|id=Euclidean_algorithm}}
| |
| | | | |
| | {{DEFAULTSORT:ゆうくりつとのこしよほう}} | | {{DEFAULTSORT:ゆうくりつとのこしよほう}} |