ユークリッドの互除法

ユークリッドの互除法は、与えられた2つの整数から始まる非負整数の列を構築するものと考えることができる。${\displaystyle r_{-2}=a}$そして${\displaystyle r_{-1}=b}$そして最終的には整数ゼロで終了します。${\displaystyle \{r_{-2}=a,\ r_{-1}=b,\ r_{0},\ r_{1},\ \cdots ,\ r_{n-1},\ r_{n}=0\}}$と${\displaystyle r_{k+1}<r_{k}.}$整数$\displaystyle r_{n-1}}$すると最大公約数となり、次のように述べることができます。${\displaystyle {\text{gcd}}(a,b)=r_{n-1}.}$このアルゴリズムは、中間剰余を構築する方法を示しています。$\displaystyle r_{k}}$前のペアに対する剰余除算によって${\displaystyle (r_{k-2},\ r_{k-1})}$整数商を求めることによって$q_k$となることによって：

${\displaystyle r_{k-2}=q_{k}\cdot r_{k-1}+r_{k}{\text{、ただし }}\ r_{k-1}>r_{k}\geq 0。}$

非負整数の列であるため${\displaystyle \{r_{k}\}}$は厳密に減少するので、最終的には終了しなければなりません。言い換えれば、$\displaystyle r_{k}\geq 0$すべての${\displaystyle k,}$そしてそれぞれ$\displaystyle r_{k}}$は、前の整数より厳密に小さい整数です。${\displaystyle r_{k-1},}$最終的にはゼロより小さい非負整数は存在し得ないため、アルゴリズムは終了しなければなりません。実際、アルゴリズムは常にn番目のステップで終了します。$\displaystyle r_n}}$ゼロに等しい。^{[ 15 ]}

例として、1071と462の最大公約数が要求されたとします。シーケンスは最初は${\displaystyle \{r_{-2}=1071,\ r_{-1}=462\}}$そして見つけるために${\displaystyle r_{0},}$整数を見つける必要があります$q0$そして$\displaystyle r_{0}<r_{-1}}$すなわち、以下の通りである。

${\displaystyle 1071=q_{0}\cdot 462+r_{0}.}$

これは商です${\displaystyle q_{0}=2}$以来${\displaystyle 1071=2\cdot 462+147.}$これは決定します$\displaystyle r_{0}=147}$そしてシーケンスは${\displaystyle \{1071,\ 462,\ r_{0}=147\}.}$次のステップは、シーケンスを続けて見つけることです$\displaystyle r_1}}$整数を見つけることによって$q_1$そして$\displaystyle r_{1}<r_{0}}$すなわち、以下の通りである。

${\displaystyle 462=q_{1}\cdot 147+r_{1}.}$

これは商です${\displaystyle q_{1}=3}$以来${\displaystyle 462=3\cdot 147+21.}$これは決定します$\displaystyle r_{1}=21}$そしてシーケンスは${\displaystyle \{1071,\ 462,\ 147,\ r_{1}=21\}.}$次のステップは、シーケンスを続けて見つけることです$\displaystyle r_2$整数を見つけることによって$q2$そして$\displaystyle r_{2}<r_{1}}$すなわち、以下の通りである。

${\displaystyle 147=q_{2}\cdot 21+r_{2}.}$

これは商です${\displaystyle q_{2}=7}$以来${\displaystyle 147=7\cdot 21+0.}$これは決定します$\displaystyle r_{2}=0}$そしてシーケンスは次のように完了します${\displaystyle \{1071,\ 462,\ 147,\ 21,\ r_{2}=0\}}$より小さい非負整数は存在しない${\displaystyle 0}$見つけることができる。最後から2番目の残り${\displaystyle 21}$したがって、要求されたGCDは次のとおりです。

${\displaystyle {\text{gcd}}(1071,\ 462)=21.}$

最初の2つの値に対する順序付けの要件をなくすことで、少し一般化することができます。${\displaystyle a}$そして${\displaystyle b.}$もし${\displaystyle a=b,}$アルゴリズムは継続し、自明に次のことを見つけるかもしれない。${\displaystyle {\text{gcd}}(a,\ a)=a}$余りのシーケンスは次のようになります${\displaystyle \{a,\ a,\ 0\}.}$もし${\displaystyle a<b,}$そうすれば、${\displaystyle a\equiv 0\cdot b+a,}$次の余りは${\displaystyle a}$それ自体、そしてそのシーケンスは${\displaystyle \{a,\ b,\ a,\ \cdots \}.}$通常、これは要件に違反するため無効となる。${\displaystyle r_{0}<r_{-1}}$しかし今、私たちは${\displaystyle a<b}$構成上、要件は自動的に満たされ、ユークリッドのアルゴリズムは通常どおり続行できます。したがって、最初の 2 つの整数間の順序を削除しても、次の剰余が常に条件を満たすため、数列が最終的に終了するという結論には影響しません。${\displaystyle r_{0}<b}$そしてすべては上記のとおり続きます。唯一変更する必要があるのは次の点です。${\displaystyle r_{k}<r_{k-1}}$のみ${\displaystyle k\geq 0,}$そして、非負整数の部分列${\displaystyle \{r_{k-1}\}}$のために${\displaystyle k\geq 0}$厳密に減少するため除外する${\displaystyle a=r_{-2}}$両方の発言から。

ステップの存在${\displaystyle N}$そのため${\displaystyle r_{N}=0}$条件から導かれる${\displaystyle |r_{i}|<|r_{i-1}|}$、 のために${\displaystyle i\geq 1}$これにより、アルゴリズムが確実に終了することが保証されます。

最後のゼロ以外の剰余${\displaystyle r_{N-1}}$等しい${\displaystyle \gcd(a,b)}$以下の性質から導かれる${\displaystyle \gcd }$

1.${\displaystyle \gcd(x,0)=x}$すべての${\displaystyle x\neq 0}$。

実際、${\displaystyle x}$そして${\displaystyle 0}$は、${\displaystyle x}$そのうち${\displaystyle x}$それ自体が最大である。

2.${\displaystyle \gcd(x,y)=\gcd(y,x-zy)}$

実際、ペアの共通約数の集合は${\displaystyle (x,y)}$そして${\displaystyle (y,x-zy)}$これらは同じである。特に、それらの最大の共通約数は同じである。

これを確認するには、${\displaystyle d}$は の公約数です${\displaystyle x}$そして${\displaystyle y}$これは、整数が存在することを意味します。${\displaystyle X,Y}$そのため${\displaystyle x=dX}$そして${\displaystyle y=dY}$したがって、${\displaystyle x-zy=dX-zdY=d(X-zY)}$、 どこ${\displaystyle X-zY}$は整数です。したがって、${\displaystyle d}$は の約数でもある${\displaystyle x-zy}$。

逆に、${\displaystyle d}$は の公約数です${\displaystyle x-zy}$そして${\displaystyle y}$すると整数が存在する${\displaystyle Z}$そして${\displaystyle Y}$そのため${\displaystyle x-zy=dZ}$そして${\displaystyle y=dY}$これから${\displaystyle x=(x-zy)+zy=dZ+zdY=d(Z+zY)}$、 どこ${\displaystyle Z+zY}$は整数です。したがって、${\displaystyle d}$は、の公約数でもある。${\displaystyle x}$そして${\displaystyle y}$。

さて、ユークリッドアルゴリズムはペアから始まります。${\displaystyle (r_{-2},r_{-1})=(a,b)}$そして各ステップで、余りのペア${\displaystyle (r_{k-2},r_{k-1})}$に置き換えられます${\displaystyle (r_{k-1},r_{k-2}-q_{k}r_{k-1})=(r_{k-1},r_{k})}$特性2は、${\displaystyle \gcd }$ペアの は不変のままです。特に、${\displaystyle \gcd }$最初のペアのうち${\displaystyle (a,b)}$そして最後のペア${\displaystyle (r_{N-1},0)}$同じです。プロパティ1を適用すると、${\displaystyle \gcd(a,b)=\gcd(r_{N-1},0)=r_{N-1}}$。

例として、ユークリッドの互除法を用いて、 a = 1071とb = 462の最大公約数を求めることができます。まず、1071から462の倍数を引いていき、余りが462未満になるまで続けます。このような倍数を 2 つ引くと ( q ₀ = 2 )、余りは147になります。

1071 = 2 × 462 + 147。

次に、 462から147の倍数を引いていき、余りが147未満になるまで続けます_。3つの倍数を引くことができます（q1 = 3）。余りは21です。

462 = 3 × 147 + 21。

次に、余りが21未満になるまで、147から21の倍数_を引いていきます。7つの倍数を引くことができます（q2 = 7）。余りは出ません。

147 = 7 × 21 + 0。

最後の余りがゼロなので、アルゴリズムは1071と462の最大公約数として21で終了します。これは、上記の素因数分解で得られたgcd(1071, 462)と一致します。表形式で手順を以下に示します。

ユークリッドの互除法は、最大公約数について上述したタイル張りのアナロジーで視覚化できます。^{[ 16 ]} a × bの長方形を正方形タイルで完全に覆うことを希望するとします。ここで、 a は2 つの数のうち大きい方です。まず、 b × bの正方形タイルを使用して長方形をタイル張りしようとします。しかし、これにより、 r ₀ < bであるr ₀ × bの残りの長方形がタイル張りされずに残ります。次に、残りの長方形をr ₀ × r _{0 の}正方形タイルでタイル張りしようとします。これにより、2 番目の残りの長方形r ₁ × r _{0が残ります。これを}r ₁ × r ₁の正方形タイルでタイル張りしようとします。以下同様です。この手順は、残りの長方形がなくなったとき、つまり、正方形タイルが前の残りの長方形を完全に覆ったときに終了します。最小の正方形タイルの辺の長さは、元の長方形の寸法の最大公約数です。例えば、隣の図の最小の正方形タイルは21×21（赤色で表示）であり、21は元の長方形の寸法である1071と462の最大公約数（緑色で表示）です。

ユークリッドアルゴリズムは、各ステップkにおいて、 2 つの数r _{k −1}とr _{k −2}から商q _kと余りr _{kを計算します。}

r _{k −2} = q _k r _{k −1} + r _k、

ここで、r _kは非負であり、r _{k −1}の絶対値より厳密に小さい。ユークリッド除法の定義の基礎となる定理は、このような商と余りが常に存在し、一意であることを保証する。^{[ 17 ]}

ユークリッドのアルゴリズムの原版では、商と余りは繰り返し減算によって求められます。つまり、r _{k −1を}r _{k −2}から繰り返し減算し、余りr _{k が}r _{k −1}より小さくなるまで続けます。その後、 r _kとr _{k −1}を交換し、このプロセスを繰り返します。ユークリッド除法では、2 つの交換間のすべてのステップを 1 つのステップに減らすことができるため、より効率的です。さらに、商は必要ないため、ユークリッド除法を剰余演算に置き換えることができます。剰余演算では余りのみが得られます。したがって、ユークリッドのアルゴリズムの反復は単純に次のようになります。

r _k = r _{k −2} mod r _{k −1}。

アルゴリズムの実装は擬似コードで表現できます。たとえば、除算ベースのバージョンは次のようにプログラムできます^{[ 18 ]}

関数gcd(a, b) while b ≠ 0 t := b b := a mod b a := t を返す

k番目の反復の開始時、変数b には最新の剰余r _{k −1}が格納され、変数aにはその前の剰余r _{k −2}が格納されます。ステップb  := a mod bは、上記の再帰式r _k ≡ r _{k −2} mod r _{k −1}と同等です。一時変数tには、次の剰余r _kが計算されている間、 r _{k −1}の値が格納されます。ループ反復の終了時、変数bには剰余r _kが格納され、変数aにはその前の剰余r _{k −1}が格納されます。

（負の入力が許容される場合、またはmod関数が負の値を返す可能性がある場合は、最後の行を に置き換える必要がありますreturn abs(a)。）

ユークリッドのオリジナル版である減算ベースのバージョンでは、余りの計算（）が繰り返し減算に置き換えられます。^{[ 19 ]}任意の整数を入力として扱う除算ベースのバージョンとは異なり、減算ベースのバージョンでは入力が正の整数で構成され、a = bのときに停止します。b := a mod b

関数gcd(a, b) a ≠ b の間a > bの場合 a := a − b それ以外 b := b − a を返す

変数aとb は_、前の剰余r _{k −1}とr _{k −2}を交互に保持します。反復の開始時にaがbより大きいと仮定すると、 r k ₋₂ > r _{k −1}なので、a はr _{k −2}に等しくなります。ループの反復中、a は前の剰余bの倍数で減算され、 a がbより小さくなるまで続きます。すると、aは次の剰余r _kになります。次に、bはaの倍数で減算され、再びaより小さくなると、次の剰余r _{k +1}が得られ、以下同様に続きます。

再帰バージョン^{[ 20 ]}は、連続する剰余の最大公約数の等価性と停止条件gcd( rN _{- 1,0} )= rN _{- 1}に基づいています。

関数gcd(a, b) b = 0 の場合はa を返す、それ以外の場合は gcd(b, a mod b)を返す

（上記と同様に、負の入力が許容される場合、またはmod関数が負の値を返す可能性がある場合は、命令return aを に置き換える必要がありますreturn max(a, −a)。）

例として、gcd(1071, 462)は、同等のgcd(462, 1071 mod 462) = gcd(462, 147)から計算されます。後者の GCD は、gcd(147, 462 mod 147) = gcd(147, 21)から計算され、これはさらにgcd(21, 147 mod 21) = gcd(21, 0) = 21から計算されます。

ユークリッドの互除法の別のバージョンでは、各ステップで得られる負の剰余が通常の正の剰余よりも小さい場合、商は1ずつ増加します。^{[ 21 ] [ 22 ]}以前は、この方程式は

r _{k −2} = q _k r _{k −1} + r _k

| r _{k −1} | > r _k > 0と仮定した。しかし、別の負の剰余e _kを計算することもできる。

r _{k −2} = ( q _k + 1) r _{k −1} + e _k

r _{k −1}  >  0または​

r _{k −2} = ( q _k – 1) r _{k −1} + e _k

r _{k −1}  <  0の場合。

r _{k を}e _kに置き換えると、| e _k | < | r _k |のとき、ユークリッドアルゴリズムの変種が得られ、

| r _k | ≤ | r _{k −1} | / 2

各段階で。

レオポルド・クロネッカーは、このバージョンがユークリッドの互除法のどのバージョンよりも少ないステップ数で済むことを示した。^{[ 21 ] [ 22 ]}より一般的には、任意の入力数aとbに対して、ステップ数が最小となるのは、q _{k が}次のように選択される場合に限ることが証明されている。${\displaystyle \left|{\frac {r_{k+1}}{r_{k}}}\right|<{\frac {1}{\varphi }}\sim 0.618,}$どこ${\displaystyle \varphi }$は黄金比である。^{[ 23 ]}

ベズーの恒等式は、 2 つの整数aとbの最大公約数gは、元の 2 つの数aとbの線形和として表すことができると述べています。^{[ 53 ]}言い換えれば、g = sa + tbとなるような整数sとt を常に見つけることができます。^{[ 54 ] [ 55 ]}

整数sとt は、ユークリッドの互除法の等式の順序を逆にすることで、商q ₀、q _{1などから計算できます。} ^{[ 56 ]}最後から 2 番目の等式から始めると、g は商q _{N −1}と、その前の 2 つの剰余r _{N −2}およびr _{N −3}で表すことができます。

g = r _{N −1} = r _{N −3} − q _{N −1} r _{N −2}。

これらの2つの余りは、同様に商と前の余りを用いて表現できます。

r _{N −2} = r _{N −4} − q _{N −2} r _{N −3}および

r _{N −3} = r _{N −5} − q _{N −3} r _{N −4}。

これらの式をr _{N −2}とr _{N −3}に代入して最初の式に代入すると、 gは剰余r _{N −4}とr _{N −5}の線形和として得られます。剰余をその前の式を含む式で代入するプロセスは、元の数aとbに到達するまで続けることができます。

r ₂ = r ₀ − q ₂ r ₁

r ₁ = b − q ₁ r ₀

r ₀ = a − q ₀ b。

すべての剰余r ₀、r ₁などを代入した後、最終的な方程式はg をaとbの線形和として表し、g = sa + tbとなります。

ユークリッドのアルゴリズム、ひいてはベズーの恒等式は、ユークリッド領域の文脈に一般化することができる。

ベズーの恒等式は、2 つの数aとbの最大公約数gのもう 1 つの定義を提供します。^{[ 12 ]}任意の 2 つの整数uとvを含むすべての数の集合ua + vbを考えます。aとbは両方ともgで割り切れるので、集合内のすべての数はgで割り切れます。言い換えれば、集合内のすべての数はgの整数倍です。これは、 aとbのすべての公約数について真です。ただし、他の公約数とは異なり、最大公約数は集合の要素です。ベズーの恒等式により、u = sおよびv = tを選択するとgが得られます。集合のすべての要素はgで割り切れなければならないため、より小さい公約数は集合の要素にはなり得ません。逆に、ベズーの恒等式の整数sとtでu = msおよびv = mtを選択すると、gの任意の倍数mが得られます。これは、ベズーの恒等式にmを掛けることで確認できます。

mg = msa + mtb。

したがって、すべての数ua + vbの集合は、gの倍数mの集合と等価です。言い換えれば、2 つの数 ( aとb ) の整数倍のすべての可能な和の集合は、 gcd( a , b )の倍数の集合と等価です。GCD は、 aとbのイデアルの生成元であると言われています。この GCD の定義は、主イデアル(単一の要素によって生成されるイデアル) と主イデアル領域(すべてのイデアルが主イデアルである領域) という現代の抽象代数概念につながりました。

この結果を利用すると、いくつかの問題を解決できます。^{[ 57 ]}例えば、体積がaとbの 2 つの計量カップを考えます。最初のカップのu倍数と 2 番目のカップのv倍数を加算/減算することで、任意の体積ua + vbを測定できます。これらの体積はすべてg = gcd( a , b )の倍数です。

ベズーの恒等式の整数sとt は、拡張ユークリッドアルゴリズムを使用して効率的に計算できます。この拡張では、ユークリッドのアルゴリズムに 2 つの再帰方程式が追加されます^{[ 58 ]。}

s _k = s _{k −2} − q _k s _{k −1}

t _k = t _{k −2} − q _k t _{k −1}

初期値とともに

s ₋₂ = 1、t ₋₂ = 0

s ₋₁ = 0、t ₋₁ = 1。

この再帰を用いると、ベズーの整数sとtはs = s _Nおよびt = t _Nで与えられ、N + 1はアルゴリズムがr _{N +1} = 0で終了するステップである。

このアプローチの妥当性は帰納法によって示すことができる。アルゴリズムのステップk − 1まで再帰式が正しいと仮定する。言い換えれば、

r _j = s _j a + t _j b

k未満のすべてのjに対して。アルゴリズムのk番目のステップは次の式を与える。

r _k = r _{k −2} − q _k r _{k −1}。

漸化式はr _{k −2}およびr _{k −1に対して正しいと仮定されているため、それらは対応する}sおよびt変数で表すことができる。

r _k = ( s _{k −2} a + t _{k −2} b ) − q _k ( s _{k −1} a + t _{k −1} b )。

この式を整理すると、ステップkの漸化式が得られます。

r _k = s _k a + t _k b = ( s _{k −2} − q _k s _{k −1} ) a + ( t _{k −2} − q _k t _{k −1} ) b。

整数sとtは、同等の行列法を用いて求めることもできる。^{[ 59 ]}ユークリッドの互除法の式列

${\displaystyle {\begin{aligned}a&=q_{0}b+r_{0}\\b&=q_{1}r_{0}+r_{1}\\&\,\,\,\vdots \\r_{N-2}&=q_{N}r_{N-1}+0\end{aligned}}}$

2×2の商行列と2次元の剰余ベクトルの積として表すことができる。

${\displaystyle {\begin{pmatrix}a\\b\end{pmatrix}}={\begin{pmatrix}q_{0}&1\\1&0\end{pmatrix}}{\begin{pmatrix}b\\r_{0}\end{pmatrix}}={\begin{pmatrix}q_{0}&1\\1&0\end{pmatrix}}{\begin{pmatrix}q_{1}&1\\1&0\end{pmatrix}}{\begin{pmatrix}r_{0}\\r_{1}\end{pmatrix}}=\cdots =\prod _{i=0}^{N}{\begin{pmatrix}q_{i}&1\\1&0\end{pmatrix}}{\begin{pmatrix}r_{N-1}\\0\end{pmatrix}}\,.}$

Mを全ての商行列の積とします。

${\displaystyle \mathbf {M} ={\begin{pmatrix}m_{11}&m_{12}\\m_{21}&m_{22}\end{pmatrix}}=\prod _{i=0}^{N}{\begin{pmatrix}q_{i}&1\\1&0\end{pmatrix}}={\begin{pmatrix}q_{0}&1\\1&0\end{pmatrix}}{\begin{pmatrix}q_{1}&1\\1&0\end{pmatrix}}\cdots {\begin{pmatrix}q_{N}&1\\1&0\end{pmatrix}}\,.}$

これにより、ユークリッドの互除法は次の形式に簡略化されます。

${\displaystyle {\begin{pmatrix}a\\b\end{pmatrix}}=\mathbf {M} {\begin{pmatrix}r_{N-1}\\0\end{pmatrix}}=\mathbf {M} {\begin{pmatrix}g\\0\end{pmatrix}}\,.}$

g をaとbの線形和として表すには、この等式の両辺に行列Mの逆行列を掛ければよい。^{[ 59 ] [ 60 ]} Mの行列式は(−1) ^{N +1}に等しい。これは、商行列の行列式の積に等しく、それぞれの行列式はマイナス 1 である。M の行列式は決してゼロにならないため、最終的な剰余のベクトルはMの逆行列を用いて解くことができる。

${\displaystyle {\begin{pmatrix}g\\0\end{pmatrix}}=\mathbf {M} ^{-1}{\begin{pmatrix}a\\b\end{pmatrix}}=(-1)^{N+1}{\begin{pmatrix}m_{22}&-m_{12}\\-m_{21}&m_{11}\end{pmatrix}}{\begin{pmatrix}a\\b\end{pmatrix}}\,.}$

上の式は

g = (−1) ^{N +1} ( m ₂₂ a − m ₁₂ b )、

ベズーの恒等式の 2 つの整数は、s = (−1) ^{N +1} m ₂₂およびt = (−1) ^N m ₁₂です。行列法は、ユークリッドアルゴリズムの各ステップで 2 つの乗算と 2 つの加算を行う同等の漸化式と同じくらい効率的です。

ベズーの等式は、数の素因数分解の一意性を示すなど、ユークリッドの互除法の多くの応用において不可欠です。 ^{[ 61 ]}これを説明するために、数L が2 つの因数uとvの積、つまりL = uvと書けるとします。別の数wもL を割り切り、 uと互いに素である場合、次の議論により、 w はvを割り切らなければなりません。uとwの最大公約数が1である場合、整数sとtが存在し、

1 = su + tw

ベズーの恒等式により、両辺にvを掛けると次の関係式が得られる。

v = suv + twv = sL + twv

w は右辺の両項を割り切るので、左辺のvも割り切るはずです。この結果はユークリッドの補題として知られています。^{[ 62 ]}具体的には、素数がL を割り切る場合、少なくともLの 1 つの因数を割り切るはずです。逆に、数wが数列a ₁、a ₂、 ...、a _nのそれぞれと互いに素である場合、wはそれらの積a ₁ × a ₂ × ... × a _nとも互いに素です。^{[ 62 ]}

ユークリッドの補題は、すべての数が素数に一意に分解できることを証明するのに十分である。^{[ 63 ]}これを示すために、逆に、Lがそれぞれm 個とn個の素因数に独立に分解できると仮定する。

L = p ₁ p ₂ ... p _m = q ₁ q ₂ ... q _n 。

仮定により、各素数p はL を割り切るので、 q 個の因数のうちの 1 つも割り切れるはずです。また、各qも素数なので、 p = qでなければなりません。p個の因数で繰り返し割っていくと、各pには対応する素数qが存在することがわかります。2 つの素因数分解は、順序を除いて同一です。数を素数に一意に分解できることは、以下に示すように、数学的証明において多くの応用例があります。

ディオファントス方程式は、解が整数に限定される方程式であり、3世紀のアレクサンドリアの数学者ディオファントスにちなんで名付けられました。^{[ 64 ]}典型的な線形ディオファントス方程式は、次の条件を満たす整数xとyを求めます。 ^{[ 65 ]}

ax + by = c

ここで、 a、b、cは与えられた整数である。これは、モジュラー演算におけるxの式として次のように表すことができる。

ax ≡ c mod b。

aとbの最大公約数をgとする。ax + byの両項はgで割り切れるので、cもgで割り切れなければならず、そうでなければこの方程式は解を持たない。両辺をc / gで割ると、この方程式はベズーの恒等式に帰着する。

sa + tb = g、

ここで、sとtは拡張ユークリッドアルゴリズムによって求めることができる。^{[ 66 ]}_{これにより、ディオファントス方程式の1つ}の解、x1 = s ( c / g )およびy1 = t ( c / g )が得_られる。

一般に、線形ディオファントス方程式には解がないか、無限個の解が存在する。[ 67 ^]後者を見つけるには、2つの解₍ x1 , _y1 )と( x2 , y2 ₎を_考える。

ax ₁ + by ₁ = c = ax ₂ + by ₂

または同等に

a ( x ₁ − x ₂ ) = b ( y ₂ − y ₁ )。

したがって、2つのx解間の最小差はb / gであり、2つのy解間の最小差はa / gである。したがって、解は次のように表すことができる。

x = x ₁ − bu / g

y = y ₁ + au / g。

u をすべての可能な整数で変化させることで、単一の解( x ₁ , y ₁ )から無限の解の族を生成できます。解が正の整数( x > 0, y > 0)である必要がある場合、有限個の解しか存在しない可能性があります。この許容される解に対する制限により、方程式の数よりも未知数が多いディオファントス方程式のシステムの一部は有限個の解を持つことができます。^{[ 68 ]}これは、解が任意の実数である線形方程式のシステムでは不可能です(不確定システムを参照)。

有限体とは、4 つの一般化された演算を持つ数の集合です。演算は加算、減算、乗算、除算と呼ばれ、交換法則、結合法則、分配法則などの通常の性質を持ちます。有限体の例としては、モジュラー演算を使用した13 個の数の集合{0,  1,  2,  ...,  12}があります。この体では、任意の数学演算 (加算、減算、乗算、除算) の結果は、13を法として簡約されます。つまり、結果が0～12 の範囲内になるまで、13の倍数が加算または減算されます。たとえば、5 × 7 = 35 mod 13 = 9 です。このような有限体は、任意の素数pに対して定義できます。より高度な定義を使用すると、素数p ^mの任意のべき乗mに対しても定義できます。有限体はしばしばガロア体と呼ばれ、GF( p )またはGF( p ^m ) と略記されます。

m個の数からなるこのような体では、すべての非ゼロ要素a は、aa ⁻¹ = a ⁻¹ a ≡ 1 mod mとなる一意のモジュラー乗法逆元a ⁻¹を持ちます。この逆元は、合同方程式ax ≡ 1 mod m ^{[ 69 ]}または同等の線形ディオファントス方程式^{[ 70 ]}を解くことによって見つけることができます。

ax + my = 1。

この方程式は、上記のようにユークリッドの互除法で解くことができます。乗法逆元を見つけることは、電子商取引で広く使用されているRSA アルゴリズムの重要なステップです。具体的には、この方程式はメッセージを復号するために使用される整数を決定します。^{[ 71 ]} RSA アルゴリズムは体ではなく環を使用しますが、乗法逆元が存在する場合は、ユークリッドの互除法を使用して乗法逆元を見つけることができます。ユークリッドの互除法は、誤り訂正符号にも他の用途があります。たとえば、ガロア体に基づくBCH 符号やリード・ソロモン符号を復号するためのBerlekamp–Massey アルゴリズムの代替として使用できます。 ^{[ 72 ]}

ユークリッドのアルゴリズムは、複数の線形ディオファントス方程式を解くためにも使用できます。^{[ 73 ]}このような方程式は、整数xを表す新しい方法を記述する中国剰余定理に現れます。整数をその桁で表す代わりに、N 個の互いに素な数の集合m _iを法とする剰余x _iで表すことができます。^{[ 74 ]}

${\displaystyle {\begin{aligned}x_{1}&\equiv x{\pmod {m_{1}}}\\x_{2}&\equiv x{\pmod {m_{2}}}\\&\,\,\,\vdots \\x_{N}&\equiv x{\pmod {m_{N}}}\,.\end{aligned}}}$

目標は、N個の剰余x _iからx を決定することです。解決策は、複数の方程式を、個々のモジュラスm _iの積であるはるかに大きなモジュラスMを持つ単一の線形ディオファントス方程式に組み合わせ、M _{i を}次のように定義することです。

${\displaystyle M_{i}={\frac {M}{m_{i}}}.}$

したがって、各M _{i は}m _iを除く すべての法の積である。解は、次の条件を満たすN 個の新しい数h _{i を見つけることに依存する。}

${\displaystyle M_{i}h_{i}\equiv 1{\pmod {m_{i}}}\,.}$

これらの数値h _iを用いると、任意の整数x は、次の式によってその剰余x _iから再構成できる。

${\displaystyle x\equiv (x_{1}M_{1}h_{1}+x_{2}M_{2}h_{2}+\cdots +x_{N}M_{N}h_{N}){\pmod {M}}\,.}$

これらの数h _iはM _iの乗法逆数であるため、前の節で説明したようにユークリッドの互除法を使用して求めることができます。

ユークリッドの互除法を用いると、すべての正の有理数の集合を、スターン・ブロコット木と呼ばれる無限二分探索木に整理することができます。 1 (分数 1/1 で表されます) を木の根元に配置し、他の任意の数a / bの位置は、ユークリッドの互除法の元の形式を用いて gcd( a , b )を計算することで見つけることができます。この方法では、各ステップで、与えられた 2 つの数のうち大きい方を小さい方との差 (余りではない) で置き換え、2 つの数が等しくなった時点で停止します。 2 つの数のうち最初の数を置き換えるユークリッドの互除法のステップは、木のノードからその右の子へのステップに対応し、2 番目の数を置き換えるステップは、木のノードからその左の子へのステップに対応します。このようにして構築されたステップのシーケンスは、a / b が既約分数で与えられているかどうかには依存せず、根元から数a / bを含むノードへのパスを形成します。^{[ 75 ]}この事実は、この木の中に各正の有理数がちょうど一度だけ現れることを証明するために使用できる。

例えば、3/4は、根号から始めて、左に1回進み、次に右に2回進むことで求めることができます。

${\displaystyle {\begin{aligned}&\gcd(3,4)&\leftarrow \\={}&\gcd(3,1)&\rightarrow \\={}&\gcd(2,1)&\rightarrow \\={}&\gcd(1,1).\end{aligned}}}$

ユークリッドの互除法は、有理数上の別の二分木であるカルキン・ウィルフ木とほぼ同じ関係にある。違いは、経路が逆になっている点である。つまり、木の根から目標への経路を生成するのではなく、目標から根への経路を生成する。

ユークリッドの互除法は連分数と密接な関係がある。^{[ 76 ]}一連の方程式は次の形式で記述できる。

${\displaystyle {\begin{aligned}{\frac {a}{b}}&=q_{0}+{\frac {r_{0}}{b}}\\{\frac {b}{r_{0}}}&=q_{1}+{\frac {r_{1}}{r_{0}}}\\{\frac {r_{0}}{r_{1}}}&=q_{2}+{\frac {r_{2}}{r_{1}}}\\&\,\,\,\vdots \\{\frac {r_{k-2}}{r_{k-1}}}&=q_{k}+{\frac {r_{k}}{r_{k-1}}}\\&\,\,\,\vdots \\{\frac {r_{N-2}}{r_{N-1}}}&=q_{N}\,.\end{aligned}}}$

右辺の最後の項は常に次の式の左辺の逆数に等しくなります。したがって、最初の 2 つの式を組み合わせて、次の式を作成できます。

${\displaystyle {\frac {a}{b}}=q_{0}+{\cfrac {1}{q_{1}+{\cfrac {r_{1}}{r_{0}}}}}\,.}$

3番目の式は分母項r ₁ / r ₀を置き換えるために使用でき、次の式が得られます。

${\displaystyle {\frac {a}{b}}=q_{0}+{\cfrac {1}{q_{1}+{\cfrac {1}{q_{2}+{\cfrac {r_{2}}{r_{1}}}}}}}\,.}$

最終的な剰余比r _k / r _{k −1}は、常に次の式を用いて、最終式まで置き換えることができます。結果は連分数になります。

${\displaystyle {\frac {a}{b}}=q_{0}+{\cfrac {1}{q_{1}+{\cfrac {1}{q_{2}+{\cfrac {1}{\ddots +{\cfrac {1}{q_{N}}}}}}}}}=[q_{0};q_{1},q_{2},\ldots ,q_{N}]\,.}$

上記の例では、gcd(1071, 462)が計算され、商q _kはそれぞれ2、3、7でした。したがって、分数1071/462は次のように書くことができます。

${\displaystyle {\frac {1071}{462}}=2+{\cfrac {1}{3+{\cfrac {1}{7}}}}=[2;3,7]}$

計算によって確認できる。

最大公約数を計算することは、ポラードのローアルゴリズム[ ^{78 ] 、}ショアのアルゴリズム^{[ 79 ]}、ディクソンの因数分解法^{[ 80 ]} 、レンストラ楕円曲線因数分解^{[ 81 ]}など、いくつかの整数因数分解アルゴリズム^{[ 77 ]}において不可欠なステップです。ユークリッドの互除法は、この最大公約数を効率的に見つけるために使用できます。連分数因数分解では、ユークリッドの互除法を使用して決定される連分数を使用します^{[ 82 ] 。}

2つの自然数aとbの最大公約数を計算するステップ数は、T ( a , b )で表される。 ^{[ 93 ]} gがaとbの最大公約数である場合、互いに素な 2 つの数mとnに対してa = mgおよびb = ng となる。     

T ( a , b ) = T ( m , n )

これは、ユークリッドアルゴリズムのすべてのステップをgで割ることによって確認できます。^{[ 94 ]}同様の議論により、 aとbに共通因子wを掛けてもステップ数は変わりません。T ( a , b ) = T ( wa , wb )。したがって、ステップ数Tは、2 つの最大公約数の大きさに応じて、T( a , b ) と T( a , b + 1 ) のように、隣接する数のペア間で大きく変化する可能性があります。   

ユークリッドの互除法の再帰的な性質により、別の式が得られる。

T ( a , b ) = 1 + T ( b , r₀ ) = 2 + T ( r₀ _, r₁ ₎ = … = N + T ( r₁N₁ - _{2 , r₁N₁ )} = N + ₁

ここで、仮定によりT ( x , 0)  = 0 である。 ^{[ 93 ]}