ユークリッドの互除法

数学において、ユークリッドの互除法（ユークリッドのあいだほうほう、英: Euclidean algorithm）^{[注 1]は、2つの}整数の最大公約数（GCD）を計算する効率的な手法である。最大公約数とは、その2つを割り切れる最大の数である。この手法は、古代ギリシャの数学者ユークリッドが『原論』（紀元前 300年頃）で初めて説明したことにちなんで名付けられた。ユークリッドの互除法は、明確に定義された規則に従って計算を実行するための段階的な手順であるアルゴリズムの一例であり、一般的に使用されているアルゴリズムの中でも最も古いものの一つである。分数を最も単純な形に簡約するために使用でき、他の多くの数論的計算や暗号計算の一部となっている。

ユークリッドの互除法は、2 つの数の最大公約数は、大きい数を小さい数との差に置き換えても変化しないという原理に基づいています。たとえば、21 は 252 と 105 の最大公約数 (GCD) です ( 252 = 21 × 12、105 = 21 × 5)。また、同じ数 21 は、105 と252 − 105 = 147の最大公約数でもあります。この置き換えにより、2 つの数のうち大きい方が小さくなるため、このプロセスを繰り返すと、2 つの数が等しくなるまで、連続して小さい数のペアが得られます。等しくなると、その数が元の 2 つの数の最大公約数になります。手順を逆にするか、拡張ユークリッドの互除法を使用すると、GCD は元の 2 つの数値の線形結合、つまり 2 つの数値の合計にそれぞれ整数を掛けたものとして表すことができます(たとえば、21 = 5 × 105 + (-2) × 252 )。GCD が常にこのように表せるという事実は、ベズーの恒等式として知られています。

上で説明したユークリッドの互除法のバージョン（ユークリッドのオリジナルの提示に従っている）では、与えられた数の一方が他方よりはるかに大きい場合、GCDを見つけるために多くの減算ステップが必要になることがあります。アルゴリズムのより効率的なバージョンでは、これらのステップが省略され、2つの数のうち大きい方の数を、小さい方の数で割ったときの余りで置き換えます（このバージョンでは、余りがゼロになるとアルゴリズムは停止します）。この改良により、アルゴリズムは小さい方の整数の桁数（基数10）の5倍を超えるステップを必要とすることはありません。これは1844年にガブリエル・ラメによって証明され（ラメの定理）、^{[1] [2]}計算複雑性理論の始まりを示しています。アルゴリズムの効率を向上させる追加の方法は、20世紀に開発されました。

ユークリッドの互除法には、理論的にも実際的にも多くの応用がある。分数を最も単純な形に簡約したり、剰余算で除算を実行したりするのに使用される。このアルゴリズムを使用した計算は、インターネット通信のセキュリティ保護に使用される暗号化プロトコルの一部を形成し、大きな合成数を因数分解してこれらの暗号システムを破る方法にも使用される。ユークリッドの互除法は、中国剰余定理に従って多重合同を満たす数を見つけるなどのディオファントス方程式を解いたり、連分数を作成したり、実数の正確な有理近似値を見つけたりするために使用できる。最後に、ラグランジュの四平方定理や素因数分解の一意性など、数論の定理を証明するための基本的なツールとしても使用できる。

元のアルゴリズムは自然数と幾何学的長さ（実数）についてのみ記述されていましたが、19世紀にはガウス整数や1変数の多項式など他の種類の数にも一般化されました。これにより、ユークリッド領域などの現代の抽象代数概念が生まれました。

ユークリッドの互除法は、2つの自然数 aとbの最大公約数 (GCD) を計算します。最大公約数g は、 aとb の両方を割り切って余りが残らない 最大の自然数です。GCD の同義語には、最大公約数(GCF)、最大公約数(HCF)、最大公約数(HCD)、最大公約数(GCM) などがあります。最大公約数は、gcd( a ,  b )または、より簡単に( a ,  b )と表記されることが多く、^{[3]後者の表記は曖昧ですが、GCD と密接に関連する}整数環のイデアルなどの概念にも使用されます。

gcd( a ,  b ) = 1の場合、aとb は互いに素である（または互いに素である）と言われます。 ^{[4]この特性は、} aまたはb自体が素数であることを意味するものではありません。^[5]たとえば、 6 と 35 は 6 = 2 × 3、 35 = 5 × 7 と因数分解されるため、素数ではありませんが、それらの素因数が異なるため、 6 と 35 は互いに素であり、 1 以外の共通因数はありません。

g = gcd( a ,  b )とする。aとb はどちらもgの倍数なので、 a  =  mgかつb  =  ngと書くことができ、これが成り立つG  >  gという大きな数は存在しない。自然数mとn は互いに素でなければならない。なぜなら、 g を大きくするためにmとnから因数分解できる共通因数はすべて、この限りではないからである。したがって、 aとb の両方を割り切れる他の任意の数cも、 g を割り切れるはずである。 aとbの最大公約数g は、他の任意の公約数cで割り切れる、aとbの唯一の（正の）公約数である。^[6]

最大公約数は次のように視覚化できます。^[7] a × bの長方形領域と、aとbの両方を正確に分割する任意の公約数cについて考えます。長方形の辺は長さcの線分に分割でき、これにより長方形は辺の長さcの正方形のグリッドに分割されます。GCD g は、これが可能なcの最大値です。説明のために、 24×60 の長方形領域は、1×1 の正方形、2×2 の正方形、3×3 の正方形、4×4 の正方形、6×6の正方形、または12×12 の正方形のグリッドに分割できます。したがって、12 は24と60の最大公約数です。24×60 の長方形領域は、 12×12 の正方形のグリッドに分割でき、一方の辺には 2 つの正方形 ( 24/12 = 2 )、もう一方の辺には 5 つの正方形 ( 60/12 = 5 ) があります。

2 つの数aとbの最大公約数は、 2 つの数に共通する素因数の積です。各素因数は、aとb の両方を割り切る回数だけ繰り返すことができます。^[8]たとえば、1386 は2 × 3 × 3 × 7 × 11に因数分解でき、3213 は3 × 3 × 3 × 7 × 17に因数分解できるため、 1386と3213の最大公約数は、63 = 3 × 3 × 7となり、これが共通の素因数の積となります ( 3 × 3は両方を割り切るため、 3 が繰り返されます)。 2 つの数に共通の素因数がない場合、それらの GCD は1 (ここでは空の積のインスタンスとして取得) になります。つまり、それらは互いに素です。ユークリッドのアルゴリズムの主な利点は、素因数を計算しなくても GCD を効率的に見つけることができることです。^{[9] [10]大きな整数の} 因数分解は計算上非常に困難な問題であると考えられており、広く使用されている多くの暗号プロトコルの安全性はその実行不可能性に基づいています。^[11]

GCD の別の定義は、高度な数学、特に環論で役立ちます。^[12] 2 つの非ゼロの数aとbの最大公約数gは、それらの最小の正の整線形結合、つまりua  +  vbの形式( uとvは整数) の最小の正の数でもあります。 aとbのすべての整線形結合の集合は、実際にはgのすべての倍数の集合( mg、ただしmは整数) と同じです。現代の数学用語では、aとbによって生成されるイデアルは、 gのみによって生成されるイデアルです (単一の要素によって生成されるイデアルは主イデアルと呼ばれ、整数のすべてのイデアルは主イデアルです)。 GCD のいくつかの特性は、実際この説明によって簡単にわかります。たとえば、aとbの任意の公約数も GCD を割り切るという事実 ( ua  +  vbの両方の項を割り切る

3つ以上の数のGCDは、すべての数に共通する素因数の積に等しい^[13]が、数のペアのGCDを繰り返し取ることによっても計算できる^[14] 。例えば、

gcd( a ,  b ,  c ) = gcd( a , gcd( b ,  c )) = gcd(gcd( a ,  b ),  c ) = gcd(gcd( a ,  c ),  b )。

したがって、2 つの整数の GCD を計算するユークリッドのアルゴリズムは、任意の数の整数の GCD を計算するのに十分です。

ユークリッドの互除法は、与えられた 2 つの整数 と で始まり、最終的に整数 0 で終了する負でない整数のシーケンスを構築するものと考えることができます。この場合、整数はGCD となり、 と表すことができます。このアルゴリズムは、次の式を満たす整数商を見つけることによって、前のペアの剰余割り算によって中間の剰余を構築する方法を示しています。 ${\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})}$${\displaystyle q_{k}}$

${\displaystyle r_{k-2}=q_{k}\cdot r_{k-1}+r_{k}{\text{, with }}\ r_{k-1}>r_{k}\geq 0.}$

非負整数のシーケンスは厳密に減少するため、最終的には終了する必要があります。言い換えると、すべての に対して、各 は前の よりも厳密に小さい整数であるため、最終的にはゼロより小さい非負整数は存在できず、したがってアルゴリズムは終了する必要があります。実際、アルゴリズムは常に n 番目のステップで がゼロに等しいときに終了します。^[15]${\displaystyle \{r_{k}\}}$${\displaystyle r_{k}\geq 0}$${\displaystyle k}$${\displaystyle r_{k}}$${\displaystyle r_{k-1}}$${\displaystyle r_{n}}$

例として、1071 と 462 の GCD が要求されているとします。シーケンスは最初は であり、 を見つけるには、次の条件を満たす整数と を見つける必要があります。 ${\displaystyle \{r_{-2}=1071,\ r_{-1}=462\}}$${\displaystyle r_{0}}$${\displaystyle q_{0}}$${\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}}$${\displaystyle 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}}$${\displaystyle q_{2}}$${\displaystyle r_{2}<r_{1}}$

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

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

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

最初の 2 つの値とに対する順序付け要件を削除することで、若干一般化できます。 の場合、アルゴリズムは続行され、剰余のシーケンスが となるため、 であることが自明にわかります。 の場合、 であるため続行することもできます。これは、次の剰余が自身であるはずであり、シーケンスは であることを示しています。通常、これは要件に違反するため無効ですが、ここでは構成により となるため、要件は自動的に満たされ、ユークリッドのアルゴリズムは通常どおり続行できます。したがって、最初の 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}$${\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}}$

ユークリッドの互除法の妥当性は、2段階の議論によって証明できる。^[16]最初のステップでは、最終的なゼロでない余りr _{N −1が}aとb の両方を割り切ることが示される。これは公約数なので、最大公約数g以下でなければならない。2番目のステップでは、 gを含むaとbの任意の公約数がr _{N −1}を割り切ることが示される。したがって、g はr _{N −1}以下でなければならない。これら2つの逆の不等式は、r _{N −1}  =  gを意味する。

r _{N −1 が}aとbの両方を割り切ることを証明するために（最初のステップ）、r _{N −1 は}その前のr _{N −2を割り切る。}

r _{N −2} = q _N r _{N −1}

最後の剰余r _Nはゼロである。r N _{−1 は、その}次の剰余r _{N −3をも割り切る。}

r _{N −3} = q _{N −1} r _{N −2} + r _{N −1}

なぜなら、 r _{N −1}は、方程式の右側の両項を割り切るからです。同じ議論を繰り返すと、 r N −1 は、 aとb を含む、先行するすべての剰余を割り切ります。先行する剰余r _{N −2}、r _{N −3}などは、余りを残すため、aとb を割り切れません。 r _{N −1 は}aとbの公約数なので、r _{N −1}  ≤  gです。

2 番目のステップでは、 aとb の両方を割り切る任意の自然数c (つまり、aとbの任意の公約数) は、余りr _{k を}割り切ります。定義により、aとb はcの倍数として表すことができます 。a  =  mcおよびb  =  ncで、mとnは自然数です。したがって、r ₀  =  a  −  q ₀ b  =  mc  −  q ₀ nc  = ( m  −  q ₀ n ) cであるため、 c は最初の余りr ₀を割り切ります。同様の議論から、c は後続の余りr ₁、r ₂なども割り切ることがわかります。したがって、最大公約数g はr _{N −1}を割り切る必要があり、これはg  ≤  r _{N −1}を意味します。議論の最初の部分でその逆 ( r _{N −1}  ≤  g ) を示したため、 g  =  r _{N −1}となります。したがって、gは後続のペアの最大公約数である：^{[17] [18]}

g = gcd( a , b ) = gcd( b , r ₀ ) = gcd( r ₀ , r ₁ ) = … = gcd( r _{N −2} , r _{N −1} ) = r _{N −1}。

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

1071 = 2 × 462 + 147 です。

次に、462 から 147 の倍数を引いて、余りが 147 未満になるまで繰り返します。3 つの倍数 ( q ₁  = 3) を引くと、余りは 21 になります。

462 = 3 × 147 + 21。

次に、147 から 21 の倍数を引いて、余りが 21 未満になるまで繰り返します。7 つの倍数 ( q ₂  = 7) を減算しても余りは残りません。

147 = 7 × 21 + 0.

最後の余りがゼロなので、アルゴリズムは 1071 と 462 の最大公約数である 21 で終了します。これは、上記の素因数分解で見つかった gcd(1071, 462) と一致します。表形式では、手順は次のとおりです。

ユークリッドの互除法は、最大公約数について上で示したタイリングのアナロジーで視覚化できます。^[19] a × b の長方形を正方形のタイルで正確に覆いたいとします。ここで、 a は2 つの数のうち大きい方です。最初にb × b の正方形タイルを使用して長方形をタイル張りしようとしますが、これによりr ₀ × b の残余長方形がタイル張りされません ( r ₀  <  b )。次に、残余長方形をr ₀ × r ₀の正方形タイルでタイル張りしようとします。これにより、2 番目の残余長方形r ₁ × r _{0が残り、これを}r ₁ × r _{1 の}正方形タイルを使用してタイル張りしようとします。このシーケンスは、残余長方形がなくなると、つまり正方形タイルが前の残余長方形を正確に覆うと終了します。最小の正方形タイルの辺の長さは、元の長方形の寸法の GCD です。たとえば、隣の図の最小の正方形タイルは 21×21 (赤で表示) であり、21 は元の長方形 (緑で表示) の寸法である 1071 と 462 の GCD です。

ユークリッドの互除法は、各ステップ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}の絶対値よりも厳密に小さい。ユークリッド除算の定義の基礎となる定理は、そのような商と余りが常に存在し、一意であることを保証する。^[20]

ユークリッドのアルゴリズムのオリジナル版では、商と余りは減算を繰り返すことによって求められます。つまり、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 です}。

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

関数gcd(a, b) 、
     b ≠ 0
        t := b
        b := a を法とするb
        t := 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) に変更する必要があります。)

ユークリッドのオリジナルのバージョンである減算ベースのバージョンでは、剰余計算（）は減算の繰り返しに置き換えられています。^{[22]任意の整数を入力として機能させる除算ベースのバージョンとは対照的に、減算ベースのバージョンでは、入力が正の整数で構成され、} 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 −2} > r _{k −1}なので、a はr _{k −2}に等しくなります。ループ反復中、a は前回の剰余bの倍数だけ減算され、aがbより小さくなります。次に、 aが次の剰余r _kになります。次に、b はaの倍数だけ減算され、再びaより小さくなると、次の剰余r _{k +1}が得られます。以下同様に続きます。

再帰バージョン^[23]は_、連続する剰余のGCDの等式と停止条件gcd( rN _{− 1,0} )=  rN ₋₁に基づいています。

関数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ずつ増加される。^{[24] [25]}以前は、式

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

各ステップで。

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

ユークリッドの互除法は、一般的に使用されている最古のアルゴリズムの 1 つです。^[27]これはユークリッドの『原論』（紀元前 300 年頃）の、具体的には第 7 巻（命題 1 ～ 2）と第 10 巻（命題 2 ～ 3）に登場します。第 7 巻では、アルゴリズムは整数に対して定式化されていますが、第 10 巻では線分の長さに対して定式化されています。（現代の用法では、そこで実数に対して定式化されたと言うでしょう。しかし、現代の用法で実数として表される長さ、面積、体積は同じ単位で測定されず、長さ、面積、体積の自然単位は存在しません。実数の概念は当時は知られていませんでした。）後者のアルゴリズムは幾何学的です。2 つの長さaとb の最大公約数は、 aとb を均等に測る最大の長さgに対応します。言い換えると、長さaとb はどちらも長さgの整数倍です。

このアルゴリズムは、おそらくユークリッドによって発見されたものではない。彼は、それ以前の数学者たちの成果を『原論』にまとめている。 ^{[28] [29]}数学者で歴史家のBL ファン・デル・ワールデンは、第 7 巻はピタゴラス学派の数学者が書いた数論の教科書に由来すると示唆している。^[30]このアルゴリズムは、おそらくクニドスのエウドクソス（紀元前 375 年頃）によって知られていた。^{[27] [31]}このアルゴリズムは、エウドクソスより古い可能性もある。^{[32] [33]これは、ユークリッドと}アリストテレスの著作で専門用語 ἀνθυφαίρεσις (逆数減算) が使われていることから判断できる。^{[34]クロード・ブレジンスキーは、}アレクサンドリアのパップスの発言に従って、このアルゴリズムをテアイテトス（紀元前417年頃-紀元前369年頃）に帰した。^[35]

数世紀後、ユークリッドの互除法はインドと中国で独立して発見され、^[36]主に天文学で生じたディオファントス方程式を解き、正確な暦を作るために使用されました。5世紀後半、インドの数学者で天文学者のアリヤバータは、このアルゴリズムを「粉砕機」と表現しました。 ^[37]おそらくディオファントス方程式を解くのに効果的だったためでしょう。^[38]中国の剰余定理の特殊なケースは、中国の書物『孫子算経』ですでに説明されていましたが、^[39]一般解は秦九紹が1247年に著した『數書九章』で発表されました。^[40]ユークリッドの互除法は、バシェの『愉快で楽しい問題』（1624年）第2版で初めて数値的に記述され、ヨーロッパで普及した。 ^{[37]ヨーロッパでは、同様にディオファントス方程式を解いたり、}連分数を展開したりするために使用された。拡張ユークリッドの互除法は、イギリスの数学者ニコラス・サンダーソンによって発表され、^[41]彼はこれを、連分数を効率的に計算する方法としてロジャー・コーツの考案であるとしている。 ^[42]

19世紀には、ユークリッドの互除法によってガウス整数やアイゼンシュタイン整数などの新しい数体系が開発された。1815年、カール・ガウスはユークリッドの互除法を使ってガウス整数の一意因数分解を実証したが、彼の研究が初めて出版されたのは1832年である。^[43]ガウスは、そのアルゴリズムを彼の著書『算術論』 （1801年出版）で言及しているが、それは連分数の方法としてのみであった。^[36] ピーター・グスタフ・ルジューン・ディリクレは、ユークリッドの互除法を数論の多くにおける基礎として説明した最初の人物であると思われる。^[44]ルジューン・ディリクレは、一意因数分解など数論の多くの結果は、ユークリッドの互除法を適用できる他のあらゆる数体系にも当てはまると指摘した。^[45]ルジューヌ・ディリクレの数論講義はリチャード・デデキントによって編集・拡張され、デデキントはユークリッドのアルゴリズムを使って代数的整数という新しい一般的な数の種類を研究した。例えば、デデキントはガウス整数の一意の因数分解を使ってフェルマーの二乗定理を初めて証明した。 ^{[46]デデキントはまた、ユークリッドのアルゴリズムの一般化バージョンを定義できる数体系である}ユークリッド領域の概念を定義した（下記参照）。19世紀末の数十年間に、ユークリッドのアルゴリズムは徐々にデデキントのより一般的なイデアル理論に影を落とされていった。 [ ^47]

ユークリッドの互除法の他の応用は19世紀に開発された。1829年、チャールズ・シュトゥルムは、この互除法が任意の区間における多項式の実根を数えるシュトゥルム連鎖法に有用であることを示した。 ^[48]

ユークリッドの互除法は、最初の整数関係アルゴリズムであり、対応する実数間の整数関係を見つける方法である。Helaman FergusonとRW Forcade（1979）のアルゴリズム^[49]やLLLアルゴリズム[ ^50]など、いくつかの新しい整数関係アルゴリズムが開発されてきた。^[51]

1969年、コールとデイビーはユークリッドの互除法に基づく2人用ゲーム「ユークリッドのゲーム」を開発した。^[52]このゲームには最適戦略がある。^[53]プレイヤーはaとbの石の2つの山からゲームを開始する。プレイヤーは順番に小さい方の山からm倍の数の石を取り除く。つまり、2つの山がxとyの石で構成されていて、xがyより大きい場合、次のプレイヤーは大きい方の山をx個の石からx − my個の石に減らすことができる。ただし、後者は負でない整数である。勝者は、1つの山から石を0個に減らした最初のプレイヤーである。^{[54] [55]}

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

整数sとtは、ユークリッドの互除法の式の順序を逆にすることで商q ₀、q ₁などから計算できる。 ^[59]最後から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}のこれらの式を最初の式に代入すると、剰余r _{N −4}とr _{N −5}の線形和としてgが得られます。剰余をその前の数を含む式に代入するプロセスは、元の数aとbに達するまで続けることができます。

r ₂ = r ₀ − q ₂ r ₁

r ₁ = b − q ₁ r ₀

r ₀ = a − q ₀ bです。

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

ユークリッドの互除法、そしてベズーの恒等式は、ユークリッド領域のコンテキストに一般化できます。

ベズーの恒等式は、 ２つの数aとbの最大公約数gの別の定義を提供する。^[12]すべての数の集合ua  +  vb（uとvは任意の２つの整数）を考える。aとb は両方ともgで割り切れるので、集合内のすべての数はgで割り切れる。言い換えれば、集合内のすべての数はgの整数倍である。これは、 aとbのすべての公約数に当てはまる。しかし、他の公約数とは異なり、最大公約数は集合のメンバーである。ベズーの恒等式により、u  =  sおよびv  =  t を選択するとgが得られる。集合のすべてのメンバーはgで割り切れる必要があるため、より小さい公約数は集合のメンバーにはならない。逆に、 gの任意の倍数m は、 u  =  msおよびv  =  mt（sおよびtはベズーの恒等式の整数）を選択することで得られる。これはベズーの恒等式にmを掛けるとわかる。

mg = msa + mtb。

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

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

ベズー恒等式の整数sとtは、拡張ユークリッド互除法を使って効率的に計算できる。この拡張はユークリッド互除法に2つの再帰方程式を追加する^[61]

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

すべてのj はk未満である。アルゴリズムの 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は、等価行列法を使って求めることもできる。^[62]ユークリッドの互除法の方程式の列

${\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 の逆行列を掛け合わせればよい。^{[62] [63]} 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回の加算を行う、同等の再帰法と同じくらい効率的です。

ベズーの等式は、数を素因数に一意に分解できることの証明など、ユークリッドの互除法の多くの応用において重要である。 ^[64]これを説明するために、数L が2つの因数uとvの積として表せるとしよう。つまり、L  =  uvである。別の数wもL を割り切れるが、 uと互いに素である場合、次の議論により、w はv を割り切れるはずである。 uとwの最大公約数が1である場合、整数sとt は次の式で求められる。

1 =ス+トゥ

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

v = suv + twv = sL + twv

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

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

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

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

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

斧+斧= c

ここで、a、b、cは与えられた整数です。これはモジュラー算術におけるxの式として書くことができます。

ax ≡ c b を法として。

g をaとbの最大公約数とする。ax  +  byの両項はgで割り切れる。したがって、c もgで割り切れる必要があり、そうでなければ方程式は解を持たない。両辺をc / gで割ると、方程式はベズーの恒等式に簡約できる 。

sa + tb = g

ここでsとtは拡張ユークリッドの互除法によって求めることができる。^[69]これにより、ディオファントス方程式の1つの解x ₁  =  s ( c / g )およびy ₁  =  t ( c / g )が得られる。

一般に、線形ディオファントス方程式には解がないか、あるいは無限個の解が存在する。^[70]後者を見つけるには、2つの解（x ₁、  y ₁）と（x ₂、  y ₂）を考える。ここで

斧₁ + 1_倍= c =斧₂ + 2_倍

または同等

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 ) であることが要求される場合、有限個の解しか存在しない可能性がある。許容される解に対するこの制限により、方程式よりも未知数が多いディオファントス方程式の一部のシステムでは、有限個の解を持つことができる。^{[71]これは、解が}任意の実数になり得る線形方程式のシステムでは不可能である(劣決定システムを参照)。

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

m個の数を持つ体では、すべての非零元aは一意のモジュラー逆数a ⁻¹を持ち、aa ⁻¹  =  a ⁻¹ a  ≡ 1 mod  mとなる。この逆数は合同方程式ax  ≡ 1 mod  m [ 72 ^]または同等の線形ディオファントス方程式^[73]を解くことで見つけることができる。

斧+私の= 1。

この方程式は、上で説明したように、ユークリッドの互除法で解くことができます。逆数を見つけることは、電子商取引で広く使用されているRSAアルゴリズムの重要なステップです。具体的には、方程式はメッセージを復号化するために使用される整数を決定します。^{[74] RSAアルゴリズムは体ではなく}環を使用しますが、逆数が存在する場合はユークリッドの互除法を使用して見つけることができます。ユークリッドの互除法は、誤り訂正符号にも応用されています。たとえば、ガロア体に基づくBCHコードとリードソロモンコードを復号するためのベルレカンプ-マッセイアルゴリズムの代替として使用できます。 ^[75]

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

${\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 つの数のうちの 2 番目の数を置き換えるステップは、木のノードからその左の子へのステップに対応します。このようにして構築されたステップのシーケンスは、a / b が最小の項で指定されているかどうかに依存せず、根から数a / b を含むノードへのパスを形成します。^[78]この事実は、各正の有理数がこの木にちょうど1回出現することを証明するために使用できます。

たとえば、3/4 はルートから始めて、左に 1 回、右に 2 回進むことで見つけることができます。

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

ユークリッドの互除法は、カルキン・ウィルフ木と呼ばれる有理数上の別の二分木とほぼ同じ関係にあります。違いは、パスが逆になっていることです。つまり、木のルートからターゲットへのパスを生成するのではなく、ターゲットからルートへのパスを生成します。

ユークリッドの互除法は連分数と密接な関係がある。^[79]連分数の方程式は次の形式で表すことができる。

${\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 _0を代入して次のように表すことができる。

${\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]}$

計算によって確認できます。

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

ユークリッドのアルゴリズムの計算効率は徹底的に研究されてきた。^[86]この効率は、アルゴリズムに必要な除算ステップの数に各ステップの計算コストを掛けたもので説明できる。ユークリッドのアルゴリズムに関する最初の解析は、 1811年のAALレイノーによるもので、^[87]入力( u、v )に対する除算ステップの数はvで制限されることを示した。後に彼はこれをv /2 + 2に改良した。その後、1841年にPJEフィンクは^[88]除算ステップの数は最大でも 2 log ₂  v  + 1 であり、したがってユークリッドのアルゴリズムは入力のサイズの多項式時間で実行されることを示しました。^[89] エミール・レジェは1837年に、入力が連続するフィボナッチ数である場合の最悪のケースを研究した。^{[89]フィンクの分析は1844年に}ガブリエル・ラメによって改良され、^[90]完了に必要なステップ数は小さい数bの10進数の桁 数hの5倍を超えることはないことが示されました。^{[91] [92]}

均一コストモデル（単一のマシンワードに収まる数値の GCD 計算の複雑さを分析するのに適している）では、アルゴリズムの各ステップには一定の時間がかかり、Lamé の分析では、合計実行時間もO ( h ) であることが示されています。ただし、より大きな数値の計算に適した計算モデルでは、アルゴリズム内の単一の剰余計算の計算コストは​​ O ( h ² ) まで大きくなる可能性があります。^[93]この場合、アルゴリズムのすべてのステップの合計時間は、伸縮級数を使用して分析でき、これもO ( h ^{2 ) であることが示されています。高速整数乗算用の}Schönhage–Strassen アルゴリズムに基づく最新のアルゴリズム手法を使用してこれを高速化することができ、GCD の準線形アルゴリズムにつながります。 ^{[94] [95]}

2つの自然数aとbのGCDを計算するステップ数はT ( a ,  b )で表すことができます。 ^[96] gがaとbのGCDである場合、 2つの互いに素な数mとnに対してa  =  mg、b  =  ngです。

T ( a , b ) = T ( m , n )である。

これはユークリッドの互除法のすべてのステップをgで割ってみればわかる。^[97]同じ議論で、aとbに共通因数wを掛けてもステップ数は変わらない：T ( a , b )= T ( wa , wb )。したがって、ステップ数Tは、2つのGCDの大きさに応じて、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 −1} ) = N + 1

ここでT ( x ,0)=0と仮定する。^[96]

ユークリッドの互除法が自然数のペアa  >  b > 0 に対してNステップを必要とする場合、これが成り立つaとb の最小の値は、それぞれフィボナッチ数F _{N +2}とF _{N +1です。} ^[98]より正確には、ユークリッドの互除法がペアa  >  bに対してNステップを必要とする場合、a  ≥  F _{N +2}およびb  ≥  F _{N +1が成り立ちます。これは}帰納法で示すことができます。^[99] N = 1の場合 、b はa を剰余なしで割り切ります。これが成り立つ最小の自然数はb  = 1 とa  = 2 で、それぞれF ₂とF _{3です。ここで、結果が}N がM − 1までのすべての値に対して成り立つと仮定します。Mステップの互除法 の最初のステップはa  =  q ₀ b  +  r ₀であり、ユークリッドの互除法は ペアb  >  r _{0に対して}M − 1 ステップを必要とします。帰納法の仮定により、b  ≥  F _{M +1}かつr ₀  ≥  F _Mとなる。したがって、a  =  q ₀ b  +  r ₀  ≥  b  +  r ₀  ≥  F _{M +1}  +  F _M  =  F _{M +2}となり、これが望ましい不等式となる。 1844年にガブリエル・ラメによって発表されたこの証明は、計算複雑性理論の始まりを表しており、^[100]フィボナッチ数列の最初の実用的応用でもある。^[98]

この結果は、ユークリッドの互除法のステップ数がその桁数（基数 10）の 5 倍を超えることは決してないことを示すのに十分である。^[101]アルゴリズムがNステップを必要とする場合、b はF _{N +1}以上であり、 F N +1 はφ ^{N −1}以上である（ φは黄金比） 。b  ≥  φ ^{N −1}なので、N  − 1 ≤ log _φ bである。 log ₁₀ φ  > 1/5 なので、 ( N  − 1)/5 < log ₁₀ φ  log _φ b  = log ₁₀ bである。したがって、N  ≤ 5 log ₁₀ bである。したがって、ユークリッドの互除法では常にO ( h )回未満の除算が必要である（hは小さい方の数bの桁数） 。

ユークリッドの互除法の平均ステップ数は3つの異なる方法で定義されています。最初の定義は、与えられた数aと、0からa  -1までの整数から等確率で選ばれたより小さい自然数bのGCDを計算するのに必要な平均時間T ( a )です^[96]

${\displaystyle T(a)={\frac {1}{a}}\sum _{0\leq b<a}T(a,b).}$

しかし、T ( a ,  b )は2つの数値のGCDによって大きく変動するため、平均関数T ( a )も同様に「ノイズが多い」ものとなる。^[102]

このノイズを減らすために、2番目の平均τ ( a )は、 aと互いに素なすべての数に対して取られます。

${\displaystyle \tau (a)={\frac {1}{\varphi (a)}}\sum _{\begin{smallmatrix}0\leq b<a\\\gcd(a,b)=1\end{smallmatrix}}T(a,b).}$

φ ( a )個の互いに素な整数がaより小さい。ここでφはオイラーのトーシェント関数である。このタウ平均はaとともに滑らかに増加する^{[103] [104]}

${\displaystyle \tau (a)={\frac {12}{\pi ^{2}}}\ln 2\ln a+C+O(a^{-1/6-\varepsilon })}$

残差誤差はa ^{−(1/6) + ε}のオーダーで、εは無限小である。この式の定数Cはポーター定数^[105]と 呼ばれ、

${\displaystyle C=-{\frac {1}{2}}+{\frac {6\ln 2}{\pi ^{2}}}\left(4\gamma -{\frac {24}{\pi ^{2}}}\zeta '(2)+3\ln 2-2\right)\approx 1.467}$

ここでγはオイラー・マスケローニ定数、ζ'はリーマンゼータ関数の微分である。^{[106] [107]}主係数(12/π ² ) ln 2は2つの独立した方法によって決定された。^{[108] [109]}

最初の平均はタウ平均からaの 約数dを足し合わせることで計算できるので^[110]

${\displaystyle T(a)={\frac {1}{a}}\sum _{d\mid a}\varphi (d)\tau (d)}$

これは次の式で近似できる^[111]

${\displaystyle T(a)\approx C+{\frac {12}{\pi ^{2}}}\ln 2\,{\biggl (}{\ln a}-\sum _{d\mid a}{\frac {\Lambda (d)}{d}}{\biggr )}}$

ここでΛ( d )はマンゴルト関数である。^[112]

3番目の平均Y ( n )は、 aとbの両方が1からnまで（均一分布で）ランダムに選択されたときに必要なステップの平均数として定義されます^[111]

${\displaystyle Y(n)={\frac {1}{n^{2}}}\sum _{a=1}^{n}\sum _{b=1}^{n}T(a,b)={\frac {1}{n}}\sum _{a=1}^{n}T(a).}$

この式にT ( a )の近似式を代入するとY ( n )の推定値が得られる^[113]

${\displaystyle Y(n)\approx {\frac {12}{\pi ^{2}}}\ln 2\ln n+0.06.}$

ユークリッド互除法の各ステップkでは、与えられた整数r _{k −2}とr _{k −1}のペアに対して商q _kと剰余r _{kが計算される。}

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

ステップあたりの計算コストは​​主にq _kを見つけることに関連しています。なぜなら、残りのr _kはr _{k −2}、r _{k −1}、q _kから素早く計算できるからです。

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

hビット数を割る計算コストは​​O ( h ( ℓ +1))に比例する。ここでℓは商の長さである。^[93]

比較すると、ユークリッドの元の減算ベースのアルゴリズムははるかに遅くなる可能性があります。1回の整数除算は、商q回の減算に相当します。aとbの比が非常に大きい場合、商は大きくなり、多くの減算が必要になります。一方、商は小さな整数になる可能性が非常に高いことが示されています。与えられた商qの確率は、 u = ( q + 1) ²の場合、およそln | u /( u − 1)|です。^[114]たとえば、商が1、2、3、または4の確率は、それぞれ約41.5%、17.0%、9.3%、および5.9%です。減算は除算よりも高速であるため、特に大きな数の場合は、^[115]減算ベースのユークリッドアルゴリズムは除算ベースのバージョンと競合します。^[116]これはユークリッドの互除法のバイナリバージョンで利用されています。 ^[117]

推定ステップ数とステップあたりの計算コストの推定値を組み合わせると、ユークリッドのアルゴリズムは、最初の2つの数aとb の平均桁数hの2乗 ( h ² ) で増加することがわかります。h ₀、h ₁、 ...、h _{N −1 は、連続する剰余}r ₀、r ₁、 ...、r _{N −1}の桁数を表します。ステップ数N はhとともに線形に増加するため、実行時間は次のように制限されます。

${\displaystyle O{\Big (}\sum _{i<N}h_{i}(h_{i}-h_{i+1}+2){\Big )}\subseteq O{\Big (}h\sum _{i<N}(h_{i}-h_{i+1}+2){\Big )}\subseteq O(h(h_{0}+2N))\subseteq O(h^{2}).}$

ユークリッドのアルゴリズムは、その単純さから、特に小さな数値に対しては実際に広く使用されています。^[118]比較のために、ユークリッドのアルゴリズムの代替手段の効率を判定することができます。

2 つの自然数aとbの GCD を求める非効率的な方法の 1 つは、それらのすべての公約数を計算することです。この場合、 GCD は最大公約数になります。公約数は、両方の数を 2 から小さい数bまでの連続した整数で割ることで求められます。この方法のステップ数はbに対して線形に、または桁数に対して指数的に増加します。もう 1 つの非効率的な方法は、一方または両方の数の素因数を求めることです。前述のように、 GCD は 2 つの数aとbが共有する素因数の積に等しくなります。^[8]現在の素因数分解の方法も非効率的です。多くの現代の暗号化システムもこの非効率性に依存しています。^[11]

バイナリGCDアルゴリズムは、コンピュータで使用されるバイナリ表現を利用して、除算をより高速な演算に置き換える効率的な代替手段です。 ^{[119] [120]}ただし、この代替手段もO ( h ²)のようにスケーリングされます。 実際のコンピュータでは、同じようにスケーリングされますが、一般的にユークリッドの互除法よりも高速です。^{[94] 2つの数値}aとbの先頭の桁のみを調べることで、追加の効率を得ることができます。^{[121] [122]バイナリアルゴリズムは他の基数（} k進アルゴリズム）に拡張でき、 ^[123]速度が最大5倍向上します。^[124] LehmerのGCDアルゴリズムは、バイナリアルゴリズムと同じ一般原理を使用して、任意の基数でのGCD計算を高速化します。

非常に大きな整数（25,000桁以上）に対する再帰的アプローチは、 Schönhage ^{[126] [127]}やStehléとZimmermann ^[128]などの準線形整数GCDアルゴリズムにつながります。これらのアルゴリズムは、上記のユークリッド互除法の2×2行列形式を利用します。これらの準線形法は、一般にO ( h log h ² log log h )としてスケールします。^{[94] [95]}

ユークリッドの互除法は2つの自然数（正の整数）の最大公約数を求めるのに用いられるが、実数や、多項式[ ^129] 、二次整数^[130]、フルヴィッツ四元数[ ¹³¹ ]などの他の数学的対象にも一般化できる。後者の場合、ユークリッドの互除法は、一意に因数分解できるという重要な性質、すなわち、そのような数は、素数に対応する既約元に一意に因数分解できるという性質を証明するのに用いられる。一意に因数分解できる性質は、数論の多くの証明に不可欠である。

ユークリッドの互除法は、ユークリッドが『原論』第10巻で述べているように、実数に適用できる。このアルゴリズムの目的は、与えられた2つの実数aとbがその整数倍となるような実数g を特定することである。つまり、 a = mgかつb = ngであり、ここでmとnは整数である。^[28]この特定は、実数aとbの間に整数関係を見つけることと同等である。つまり、 sa + tb = 0となる整数sとt を決定する。このような等式が可能な場合、aとb は通約可能な長さと呼ばれ、そうでない場合は通約不可能な長さと呼ばれる。^{[132] [133]}

実数ユークリッド互除法は、整数ユークリッド互除法とは2つの点で異なります。まず、剰余r _kは実数ですが、商q _kは前と同様に整数です。次に、アルゴリズムは有限回数Nで終了することが保証されていません。終了する場合、分数a / bは有理数、つまり2つの整数の比 になります。

${\displaystyle {\frac {a}{b}}={\frac {mg}{ng}}={\frac {m}{n}},}$

は有限連分数[ q ₀ ; q ₁ , q ₂ , ..., q _N ]として記述できます。アルゴリズムが停止しない場合、分数a / b は無理数であり、無限連分数[ q ₀ ; q ₁ , q 2 , …]で記述できます。^[134]無限連分数の例としては、黄金比 φ = [1; 1, 1, ...]や2 の平方根√ 2 = [1; 2, 2, ...]など_があります。^[135] 2 つの実数の比a / bはほとんどすべて無理数であるため、アルゴリズムが停止する可能性は低いです。 ^[136]

無限連分数は、ステップk [ q ₀ ; q ₁ , q ₂ , ..., q _k ]で切り捨てられ、 kが増加するにつれて改善されるa / bの近似値が得られる。近似値は収束関数m _k / n _kで記述され、分子と分母は互いに素であり、再帰関係に従う。

${\displaystyle {\begin{aligned}m_{k}&=q_{k}m_{k-1}+m_{k-2}\\n_{k}&=q_{k}n_{k-1}+n_{k-2},\end{aligned}}}$

ここで、m ₋₁ = n ₋₂ = 1およびm ₋₂ = n ₋₁ = 0は再帰の初期値である。収束するm _k / n _kは分母がn _kであるa / bの最良の有理数近似値である：^[137]

${\displaystyle \left|{\frac {a}{b}}-{\frac {m_{k}}{n_{k}}}\right|<{\frac {1}{n_{k}^{2}}}.}$

単一変数xの多項式は、加算、乗算、因数分解して、整数の素数に相当する既約多項式にすることができます。2つの多項式a ( x )とb ( x )の最大公約多項式g ( x )は、それらの共有既約多項式の積として定義され、ユークリッドのアルゴリズムを使用して識別できます。^[129]基本的な手順は整数の場合と同様です。各ステップkで、商多項式q _k ( x )と剰余多項式r _k ( x )が、再帰方程式を満たすように識別されます。

${\displaystyle r_{k-2}(x)=q_{k}(x)r_{k-1}(x)+r_{k}(x),}$

ここでr ₋₂ ( x ) = a ( x )かつr ₋₁ ( x ) = b ( x )である。各商多項式は、各剰余がゼロであるか、その前の多項式の次数よりも小さい次数を持つように選択される：deg[ r _k ( x )] < deg[ r _{k −1} ( x )] 。次数は非負の整数であり、各ステップで減少するため、ユークリッドの互除法は有限数のステップで終了する。最後のゼロでない剰余は、元の2つの多項式a ( x )とb ( x )の最大公約数である。^[138]

例えば、次の2つの4次多項式を考えてみましょう。それぞれ2つの2次多項式に因数分解されます。

${\displaystyle {\begin{aligned}a(x)&=x^{4}-4x^{3}+4x^{2}-3x+14=(x^{2}-5x+7)(x^{2}+x+2)\qquad {\text{and}}\\b(x)&=x^{4}+8x^{3}+12x^{2}+17x+6=(x^{2}+7x+3)(x^{2}+x+2).\end{aligned}}}$

a ( x ) をb ( x )で割ると、余りr ₀ ( x ) = x ³ + (2/3) x ² + (5/3) x − (2/3)が得られます。次のステップでは、b ( x )をr ₀ ( x )で割ると、余りr ₁ ( x ) = x ² + x + 2が得られます。最後に、r ₀ ( x ) をr ₁ ( x )で割ると余りが 0 になり、r ₁ ( x )がa ( x )とb ( x )の最大公約数多項式であり、因数分解と一致していることがわかります。

上で説明した整数への応用の多くは、多項式にも適用できます。^[139]ユークリッドの互除法は、多項式の線形ディオファントス方程式や中国剰余問題を解くのに使用できます。また、多項式の連分数も定義できます。

多項式ユークリッド互除法には、与えられた実数区間内にある多項式の零点を数える方法であるシュトゥルム連鎖などの他の応用もある。^{[140]これは、}制御理論におけるラウス・フルヴィッツの安定基準など、いくつかの分野で応用されている。^[141]

最後に、多項式の係数は整数、実数、複素数から引き出される必要はない。例えば、係数は、上で述べた有限体GF( p )のような一般体から引き出される。ユークリッドの互除法とその応用に関する対応する結論は、そのような多項式に対しても成り立つ。^[129]

ガウス整数は、 α = u + vi の形式の複素数であり、uとvは通常の整数^{[注 2]}、i は負の 1 の平方根です。^[142]ユークリッドの互除法の類似物を定義すると、上記の議論により、ガウス整数は一意に因数分解できることがわかります。^[43]この一意の因数分解は、すべてのピタゴラスの三つ組を導出したり、 2つの平方数の和に関するフェルマーの定理を証明したりするなど、多くのアプリケーションで役立ちます。^[142]一般に、ユークリッドの互除法はこのようなアプリケーションで便利ですが、必須ではありません。たとえば、定理は他の議論によって証明できる場合がよくあります。

2つのガウス整数αとβに対して開発されたユークリッドの互除法は、通常の整数に対するものとほぼ同じであるが^{[143] 、2つの点で異なる。前と同様に、} r ₋₂ = αおよびr ₋₁ = βとし、各ステップkでのタスクは、商q _kと剰余r _kを特定して、

${\displaystyle r_{k}=r_{k-2}-q_{k}r_{k-1},}$

ここで、すべての剰余は、その前の剰余よりも厳密に小さい: | r _k | < | r _{k −1} |。最初の違いは、商と剰余自体がガウス整数であり、したがって複素数であることです。商q _{k は}、通常、正確な比の実部と複素数部 (複素数α / βなど) を最も近い整数に丸めることで求められます。^[143] 2番目の違いは、1つの複素剰余が他の複素剰余よりも「小さくなる」方法を定義する必要があることです。これを行うには、ノルム関数 f ( u + vi ) = u ² + v ²が定義され、すべてのガウス整数u + vi を通常の整数に変換します。ユークリッドアルゴリズムの各ステップkの後、剰余f ( r _k )のノルムは、前の剰余f ( r _{k −1} )のノルムよりも小さくなります。ノルムは非負の整数であり、ステップごとに減少するため、ガウス整数に対するユークリッドの互除法は有限数のステップで終了します。^[144]最終的なゼロでない剰余はgcd( α , β )であり、これはαとβ の両方を割り切る最大ノルムのガウス整数です。これは単位±1または± iによる乗算を除き一意です。^[145]

ユークリッドの互除法の他の応用の多くはガウス整数にも応用できる。例えば、ガウス整数の線形ディオファントス方程式や中国剰余問題を解くのに使える。^[146]ガウス整数の連分数も定義できる。^[143]

加算と乗算で表される2つの二項演算による元の集合は、それが可換環Rを形成し、大まかに言えば、一般化ユークリッドアルゴリズムを実行できる場合、ユークリッド領域と呼ばれます。 ^{[147] [148]このような環の2つの演算は、通常の算術の加算と乗算である必要はなく、}数学的な群やモノイドの演算など、より一般的なものでもかまいません。ただし、これらの一般的な演算は、可換性、結合性、分配法則など、通常の算術を支配する多くの法則を尊重する必要があります。

一般化ユークリッドの互除法では、ユークリッド関数、すなわち、Rから非負整数の集合への写像f が必要であり、 R内の任意の 2 つの非ゼロ要素aおよびbに対して、 a = qb + rかつf ( r ) < f ( b )となるようなR内のqおよびr が存在する。^{[149]このような写像の例としては、整数の絶対値、}単変数多項式の次数、および上記のガウス整数のノルムがある。^{[150] [151]}基本原理は、アルゴリズムの各ステップでfが容赦なく減少するということである。したがって、f を有限回数しか減少できない場合、アルゴリズムは有限回数のステップで停止しなければならない。この原理は、非負整数の整列特性に依存しており、これは、すべての空でない非負整数の集合には最小のメンバーが存在することを主張する。^[152]

算術の基本定理は、任意のユークリッド領域に適用されます。ユークリッド領域の任意の数は、一意に既約元に因数分解できます。任意のユークリッド領域は一意因数分解領域(UFD) ですが、その逆は成り立ちません。^[152]ユークリッド領域と UFD は、2 つの数の最大公約数が常に存在する領域であるGCD 領域のサブクラスです。 ^[153]言い換えると、最大公約数は存在する可能性があります (領域内のすべての要素のペアに対して) が、ユークリッドアルゴリズムを使用してそれを見つけることはできない場合があります。ユークリッド領域は常に主イデアル領域(PID)、つまりすべてのイデアルが主イデアルである整域です。^[154]繰り返しますが、逆は成り立ちません。すべての PID がユークリッド領域であるわけではありません。

ユークリッド領域の一意な因数分解は、多くの用途で有用である。例えば、ガウス整数の一意な因数分解は、すべてのピタゴラス数列の公式を導出したり、 2つの平方数の和に関するフェルマーの定理を証明するのに便利である。^[142]一意な因数分解は、ジョセフ・リウヴィルの示唆に基づいてユークリッドの互除法の効率を分析した同じ数学者ガブリエル・ラメが1847年に発表したフェルマーの最終定理の証明の試みにおいても重要な要素であった。 ^{[155]ラメのアプローチでは、} x + ωyの形式の数の一意な因数分解が必要であった。ここで、xとy は整数であり、ω = e ^{2 iπ / n}は1のn乗根、つまりω ⁿ = 1である。このアプローチは、 nがいくつかの値（ n = 3、アイゼンシュタイン整数など）の場合は成功するが、一般にそのような数は一意に因数分解されない。いくつかの円分体における一意に因数分解できないというこの失敗は、エルンスト・クンマーにイデアル数の概念をもたらし、後にリチャード・デデキントにイデアルをもたらした。^[156]

二次整数環はユークリッド領域を説明するのに役立ちます。二次整数はガウス整数の一般化であり、虚数単位 iが数ωに置き換えられます。したがって、それらはu + vωという形式を持ちます。ここでuとvは整数で、ω はパラメータDに応じて2つの形式のいずれかになります。Dが4の倍数プラス1に等しくない場合は、

${\displaystyle \omega ={\sqrt {D}}.}$

しかし、Dが4の倍数プラス1に等しい場合、

${\displaystyle \omega ={\frac {1+{\sqrt {D}}}{2}}.}$

関数f が、上記のガウス整数を順序付けるために使用されるようなノルム関数に対応する場合、その定義域はノルムユークリッドと呼ばれます。 二次整数のノルムユークリッド環は、 Dが値 −11、−7、−3、−2、−1、2、3、5、6、7、11、13、17、19、21、29、33、37、41、57、または 73 のいずれかである環とまったく同じです。^{[157] [158]} D = −1およびD = −3の場合は、それぞれガウス整数とアイゼンシュタイン整数になります。

f が任意のユークリッド関数であることが許される場合、その定義域がユークリッドとなるDの可能な値のリストはまだわかっていない。^[159]ノルムユークリッドでないユークリッド定義域の最初の例 ( D = 69 ) は 1994 年に発表された。^{[159] 1973 年に Weinberger は、}一般化リーマン予想が成り立つ場合、 D > 0の二次整数環がユークリッドであるためには、それが主イデアル定義域である必要があることを証明した。^[130]

ユークリッドのアルゴリズムは、フルヴィッツ四元数の集合のような非可換環にも適用できる。^{[131] [160]} αとβ をそのような環の2つの元としよう。環内のξとη を適当に選んでα = ξδかつβ = ηδ とすれば、それらは共通の右約数δ を持つ。同様に、環内のξとη を適当に選んでα = dξかつβ = dη とすれば、それらは共通の左約数を持つ。乗算は可換ではないため、ユークリッドのアルゴリズムには右約数用と左約数の2つのバージョンがある。^{[131] [160]右約数を選択すると、ユークリッドのアルゴリズムで}gcd( α , β )を求める最初のステップは次のように書ける。

${\displaystyle \rho _{0}=\alpha -\psi _{0}\beta =(\xi -\psi _{0}\eta )\delta ,}$

ここで、ψ _{0 は}商、ρ _{0 は}余りを表す。ここで商と余りは、非可換な場合のユークリッド領域のユークリッド関数と同様に定義される「ユークリッド関数」Nに対して、余りがN ( ρ ₀ ) < N ( β )となるように選択される。^{[160]この式は、} αとβの任意の共通右約数は、同様に余りρ ₀の共通約数であることを示す。左約数に対する類似の式は次のようになる。

${\displaystyle \rho _{0}=\alpha -\beta \psi _{0}=\delta (\xi -\eta \psi _{0}).}$

どちらの選択でも、最大公約数が特定されるまで、上記のプロセスが繰り返される。ユークリッド領域と同様に、剰余ρ ₀の「サイズ」（正式にはそのユークリッド関数または「ノルム」）はβより厳密に小さくなければならず、 ρ ₀の可能なサイズは有限数のみであるため、アルゴリズムは確実に終了する。^[161]

GCDの結果の多くは非可換数にも適用できる。例えば、ベズーの恒等式は、右gcd( α , β )はαとβの線形結合として表現できると述べている。^[162]言い換えれば、σとτという数があり、

${\displaystyle \Gamma _{\text{right}}=\sigma \alpha +\tau \beta .}$

左 GCD の類似の恒等式はほぼ同じです。

${\displaystyle \Gamma _{\text{left}}=\alpha \sigma +\beta \tau .}$

ベズーの恒等式はディオファントス方程式を解くのに使用できる。例えば、ラグランジュの四平方定理の標準的な証明の一つである、すべての正の整数は4つの平方の和として表すことができるという証明は、このように四元数GCDに基づいている。^[161]

• ユークリッドリズム、ユークリッドのアルゴリズムを使用して音楽のリズムを生成する方法

• Bueso, José; Gómez-Torrecillas, José; Verschoren, Alain (2003)。非可換代数のアルゴリズム手法: 量子群への応用。数学的モデリング: 理論と応用。第 17 巻。Kluwer Academic Publishers、ドルドレヒト。doi :10.1007 / 978-94-017-0285-0。ISBN 1-4020-1402-3. MR  2006329.
• コーエン、H. (1993)。計算代数的数論講座。ニューヨーク：シュプリンガー・フェアラーク。ISBN 0-387-55640-0。
• コーン、H. (1962)。上級数論。ニューヨーク：ドーバー。ISBN 0-486-64023-X。
• Cox, D. ; Little, J.; O'Shea, D. (1997)。イデアル、多様体、アルゴリズム: 計算代数幾何学と可換代数の入門 (第 2 版)。Springer- Verlag。ISBN 0-387-94680-2。
• Crandall, R. ; Pomerance, C. (2001).素数: 計算の観点(第 1 版). ニューヨーク: Springer-Verlag. ISBN 0-387-94777-9。
• ルジューヌ・ディリクレ、PG (1894)。リチャード・デデキント（編）。 Vorlesungen über Zahlentheorie (整数論の講義) (ドイツ語)。ブラウンシュヴァイク: Vieweg. LCCN  03005859。OCLC 490186017  。。「Vorlesungen uber Zahlentheorie」も参照
• Knuth, DE (1997)。『コンピュータプログラミングの技法』第2巻: 半数値アルゴリズム（第3版）。Addison– Wesley。ISBN 0-201-89684-2。
• LeVeque、WJ (1996) [1977]。整数論の基礎。ニューヨーク：ドーバー。ISBN 0-486-68906-9。
• モリン、RA (2008)。応用を伴う基礎数論（第2版）。ボカラトン：チャップマン＆ホール/CRC。ISBN 978-1-4200-6659-3。
• オーレ、O.（1948）「数論とその歴史」ニューヨーク：マグロウヒル。
• Rosen, KH (2000).初等数論とその応用(第 4 版). マサチューセッツ州レディング: Addison–Wesley. ISBN 0-201-87073-8。
• シュローダー、M. (2005)。科学とコミュニケーションにおける数論（第4版）。シュプリンガー・フェアラーク。ISBN 0-387-15800-6。
• スターク、H. (1978)。数論入門。MIT 出版。ISBN 0-262-69060-8。
• スティルウェル、J. (1997)。『数と幾何学』ニューヨーク：シュプリンガー・フェアラーク。ISBN 0-387-98289-2。
• スティルウェル、J. (2003)。『数論の要素』ニューヨーク：シュプリンガー・フェアラーク。ISBN 0-387-95587-9。
• Tattersall, JJ (2005)。『9章からなる初等数論』。ケンブリッジ：ケンブリッジ大学出版局。ISBN 978-0-521-85014-8。

• ユークリッドのアルゴリズムのデモンストレーション
• Weisstein、Eric W.「ユークリッドの互除法」。MathWorld。
• ユークリッドのアルゴリズム
• PlanetMathのユークリッドのアルゴリズム。
• MathPages のユークリッドの互除法
• ユークリッドのゲームをカット・ザ・ノットで
• 音楽とユークリッドのアルゴリズム