最大公約数

数学において、2つ以上の整数（いずれも0ではない）の最大公約数（GCD）は、最大公約数（GCF）とも呼ばれ、それぞれの整数を割り切る最大の正の整数です。2つの整数x、yに対して、 xとyの最大公約数はと表記されます。例えば、8と12の最大公約数は4、つまりgcd(8, 12) = 4です。^{[ 1 ] [ 2 ]}${\displaystyle \gcd(x,y)}$

「最大公約数」という名称では、形容詞「最大」を「最高」に、「除数」を「因数」に置き換えることができるため、他の名称としては最大公約数（HCF）などがあります^{。[ 3 ] [ 4 ] [ 5 ] [ 6 ]}歴史的には、同じ概念の他の名称として最大公約数などがあります。^{[ 7 ]}

この概念は、多項式（多項式の最大公約数を参照）や他の可換環（以下の§ 可換環を参照）に拡張できます。

概要

意味

整数aとbの最大公約数（GCD）は、少なくとも一方が0でない整数において、d が a と b の両方の約数となる最大の正の整数dである。つまり、a = deかつb = dfとなる整数eとfが存在し、d がそのような最大の整数である。 aとbの最大公約数は、一般にgcd( a , b )と表記される。^{[ 8 ]}

aとbのいずれかがゼロの場合、GCD は非ゼロ整数の絶対値となります。gcd ( a , 0) = gcd(0, a ) = | a | 。このケースはユークリッド互除法の終了ステップとして重要です。

上記の定義はgcd(0, 0) を定義するのには不適切です。なぜなら0 × n = 0となる最大の整数n は存在しないからです。しかし、最大が割り切れる関係の文脈で理解されるならば、ゼロはそれ自身の最大の約数なので、gcd(0, 0)は一般に0と定義されます。これにより、 GCD の通常の恒等式、特にベズーの恒等式、すなわちgcd( a , b )が{ a , b }と同じイデアルを生成するという恒等式が維持されます。^{[ 9 ] [ 10 ] [ 11 ]}この規則は多くのコンピュータ代数システムで採用されています。^{[ 12 ]}ただし、 gcd(0, 0)を未定義のままにする著者もいます。^{[ 13 ]}

aとbの GCD は、割り切れるという順序関係における、それらの最大公約数です。これは、 aとbの公約数がそれらの GCD の約数と完全に一致することを意味します。これは通常、ユークリッドの補題、算術の基本定理、またはユークリッドの互除法を用いて証明されます。これが、GCD の概念を一般化する際に用いられる「最大」の意味です。

例

数字 54 は、2 つの整数の積としていくつかの方法で表現できます。

${\displaystyle 54\times 1=27\times 2=18\times 3=9\times 6.}$

したがって、54の約数の完全なリストは1、2、3、6、9、18、27、54です。同様に、24の約数は1、2、3、4、6、8、12、24です。これらの2つのリストに共通する数は、54と24の公約数です。

${\displaystyle 1,2,3,6.}$

これらのうち、最大のものは 6 なので、これが最大公約数となります。

${\displaystyle \gcd(54,24)=6.}$

この方法で2つの数の全ての約数を計算するのは、通常、特に多くの約数を持つ大きな数の場合は効率的ではありません。より効率的な方法は、§ 計算で説明されています。

互いに素な数

2つの数の最大公約数が1である場合、その数は互いに素である、あるいは互いに素であると呼ばれます。^{[ 14 ]}例えば、9と28は互いに素です。

幾何学的な視点

24 x 60 の長方形は、12 x 12 の正方形タイル 10 個で覆われます。ここで、12 は 24 と 60 の最大公約数です。より一般的には、a x bの長方形は、 cがaとbの公約数である場合にのみ、辺の長さが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）を配置します。

アプリケーション

分数の約分

最大公約数は分数を最小の項に約すのに便利です。^{[ 15 ]}例えば、gcd(42, 56) = 14なので、

${\displaystyle {\frac {42}{56}}={\frac {3\cdot 14}{4\cdot 14}}={\frac {3}{4}}.}$

最小公倍数

両方ともゼロではない2つの整数の最小公倍数は、最大公約数から次の関係を使って計算できる。

${\displaystyle \operatorname {lcm} (a,b)={\frac {|a\cdot b|}{\operatorname {gcd} (a,b)}}.}$

計算

素因数分解の使用

最大公約数は、 2つの数の素因数分解を求め、因数を比較することで計算できます。例えば、gcd(48, 180)を計算する場合、素因数分解は 48 = 2 ⁴  · 3 ¹、 180 = 2 ²  · 3 ²  · 5 ¹となります。GCD は 2 ^min(4,2)  · 3 ^min(1,2)  · 5 ^min(0,1) = 2 ²  · 3 ¹  · 5 ⁰ = 12 です。対応する LCM は 2 ^max(4,2)  · 3 ^max(1,2)  · 5 ^max(0,1) = 2 ⁴  · 3 ²  · 5 ¹ = 720 です。

実際には、素因数分解の計算に時間がかかりすぎるため、この方法は小さい数値に対してのみ実行可能です。

ユークリッドのアルゴリズム

ユークリッドが最大公約数を計算するために導入した方法は、 a > bとなる2 つの正の整数aとbが与えられたとき、 a と b の公約数はa – bとbの公約数と同じであるという事実に基づいています。

したがって、2 つの正の整数の最大公約数を計算するユークリッド法は、大きい方の数をその数の差で置き換え、2 つの数が等しくなるまでこれを繰り返すというものです。これが最大公約数です。

例えば、gcd(48,18)を計算するには次のようにします。

${\displaystyle {\begin{aligned}\gcd(48,18)\quad &\to \quad \gcd(48-18,18)=\gcd(30,18)\\&\to \quad \gcd(30-18,18)=\gcd(12,18)\\&\to \quad \gcd(12,18-12)=\gcd(12,6)\\&\to \quad \gcd(12-6,6)=\gcd(6,6).\end{aligned}}}$

したがってgcd(48, 18) = 6となります。

この方法は、一方の数値がもう一方の数値よりも大幅に大きい場合、非常に遅くなる可能性があります。そのため、一般的には以下の方法が推奨されます。

ユークリッドの互除法

ユークリッドの互除法を用いて62と36の最大公約数である2を求めるアニメーション

より効率的な方法はユークリッドの互除法です。これは、2 つの数値aとbの差を、 aとbのユークリッド除算(剰余付き除算とも呼ばれます) の剰余で置き換える変種です。

この余りをa mod bとして表し、アルゴリズムは( a、b )を( b、a mod b )に繰り返し置き換え、そのペアが( d、 0)になるまで続けます。ここで、dは最大公約数です。

たとえば、gcd(48,18)を計算する場合、計算は次のようになります。

${\displaystyle {\begin{aligned}\gcd(48,18)\quad &\to \quad \gcd(18,48{\bmod {1}}8)=\gcd(18,12)\\&\to \quad \gcd(12,18{\bmod {1}}2)=\gcd(12,6)\\&\to \quad \gcd(6,12{\bmod {6}})=\gcd(6,0).\end{aligned}}}$

これもgcd(48, 18) = 6となります。

バイナリGCDアルゴリズム

バイナリ GCD アルゴリズムは、ほとんどのコンピューターで使用されている数値のバイナリ表現に特別に適応したユークリッドのアルゴリズムの変種です。

2進GCDアルゴリズムは、計算中に遭遇するすべての偶数を2で割る点で、ユークリッドのアルゴリズムと本質的に異なります。その効率性は、2進表現において、パリティテストは最右端の桁をテストすること、そして2で割ることは最右端の桁を削除することで構成されるという事実に起因しています。

方法は次の通りで、 GCD を求める 2 つの正の整数 aとbから始めます。

1. aとbが両方とも偶数の場合、少なくともどちらかが奇数になるまで両方を 2 で割ります。この割り算のペアの数をdとします。
2. aが偶数の場合は、奇数になるまで 2 で割ります。
3. bが偶数の場合は、奇数になるまで 2 で割ります。

   ここで、aとbは両方とも奇数であり、計算の最後まで奇数のままである。

4. a ≠ bの 場合
   • a > bの場合、 a をa – bに置き換え、 a が奇数になるまでその結果を 2 で割ります( aとbはどちらも奇数なので、少なくとも 1 回は 2 で割ります)。
   • a < bの場合、 b をb – aに置き換え、 b が奇数になるまでその結果を 2 で割ります。
5. ここで、a = bであり、最大公約数は${\displaystyle 2^{d}a.}$

ステップ1では、dを aとb を割り切る最大の2のべき乗、つまり最大公約数として決定します。どのステップもaとbの奇数公約数の集合を変更しません。これは、アルゴリズムが停止した時点で結果が正しいことを示しています。各ステップで少なくとも1つのオペランドが少なくとも2で割られるため、アルゴリズムは最終的に停止します。さらに、 2で割る回数、つまり減算の回数は、最大で総桁数になります。

例: ( a , b , d ) = (48, 18, 0) → (24, 9, 1) → (12, 9, 1) → (6, 9, 1) → (3, 9, 1) → (3, 3, 1) 。したがって、元の GCD は2 ^d = 2 ¹とa = b = 3の積 6 になります。

バイナリGCDアルゴリズムは実装が非常に簡単で、バイナリコンピュータ上で特に効率的です。その計算量は

${\displaystyle O((\log a+\log b)^{2}).}$

この複雑さの二乗は、2による除算と減算に、入力の ビット数に比例した時間がかかるという事実から生じます。

計算の複雑さは通常、入力の長さnで表されます。ここでは、この長さはn = log a + log bであり、したがって計算の複雑さは

${\displaystyle O(n^{2})}$ 。

レーマーのGCDアルゴリズム

レーマーのアルゴリズムは、ユークリッドのアルゴリズムによって生成される初期の商は最初の数桁のみに基づいて決定できるという観察に基づいています。これは、コンピュータ ワードよりも大きな数値に役立ちます。基本的には、通常 1 つまたは 2 つのコンピュータ ワードを形成する最初の桁を抽出し、商が元の数値で得られる商と同じであることが保証されている限り、これらの小さな数値に対してユークリッドのアルゴリズムを実行します。商は、元の数値を縮小するために、小さな 2 行 2 列の変換行列 (単一ワードの整数の行列) に収集されます。このプロセスは、数値が十分に小さくなり、バイナリ アルゴリズム (以下を参照) がより効率的になるまで繰り返されます。

このアルゴリズムは、非常に大きな数に対する演算回数を減らし、ほとんどの演算にハードウェア演算を使用できることから、速度が向上します。実際、ほとんどの商は非常に小さいため、ユークリッド互除法のかなりのステップを2行2列の単一ワード整数の行列にまとめることができます。レーマーのアルゴリズムは、商が大きすぎる場合、ユークリッド互除法の1回の反復、つまり大きな数のユークリッド除算にフォールバックする必要があります。

その他の方法

トーマ関数

aとbが両方ともゼロでない場合、 aとbの最大公約数は、aと bの最小公倍数(LCM)を使用して計算できます。

${\displaystyle \gcd(a,b)={\frac {|a\cdot b|}{\operatorname {lcm} (a,b)}}}$ 、

しかし、より一般的には、LCM は GCD から計算されます。

トーマエ関数fを用いると、

${\displaystyle \gcd(a,b)=af\left({\frac {b}{a}}\right),}$

これは、 aおよびb の有理数または通約可能な実数 に一般化されます。

キース・スラヴィンは奇数a ≥ 1に対して次を示した。

${\displaystyle \gcd(a,b)=\log _{2}\prod _{k=0}^{a-1}(1+e^{-2i\pi kb/a})}$

これは複素数bに対して評価できる関数である。^{[ 16 ]}ヴォルフガング・シュラムは、

${\displaystyle \gcd(a,b)=\sum \limits _{k=1}^{a}\exp(2\pi ikb/a)\cdot \sum \limits _{d\left|a\right.}{\frac {c_{d}(k)}{d}}}$

は変数bのすべての正の整数aに対する整関数であり、c _d ( k )はラマヌジャンの和である。^{[ 17 ]}

複雑

最大公約数の計算の複雑さは広く研究されてきた。[ 18 ^{]ユークリッドの互除法と}乗算・除算の基本アルゴリズムを用いると、最大nビットの2つの整数の最大公約数の計算はO ( n^ ² )となる。これは、最大公約数の計算は、定数倍まで乗算と同じ複雑さを持つことを意味する。

しかし、高速な乗算アルゴリズムを使用する場合、ユークリッドの互除法を修正して計算量を改善できますが、最大公約数の計算は乗算よりも遅くなります。より正確には、nビットの2つの整数の乗算にT ( n )の時間がかかる場合、最大公約数を求める既知の最速アルゴリズムの計算量はO ( T ( n )logn )です。これは、既知の最速アルゴリズムの計算量はO ( n (logn ) 2 ⁾であることを意味します。

前述の複雑性は、通常の計算モデル、具体的にはマルチテープ チューリング マシンとランダム アクセス マシンに有効です。

したがって、最大公約数の計算は、準線形時間で解ける問題のクラスに属する。ましてや、対応する決定問題は、多項式時間で解ける問題のクラスPに属する。GCD 問題はNCに属するかどうかはわかっていないため、効率的に並列化する方法もわかっていない。また、 P 完全かどうかもわかっていないため、GCD 計算を効率的に並列化できる可能性は低い。Shallcross らは、関連問題 (ユークリッドの互除法の実行中に生じる剰余列を決定する EUGCD) が、2 変数の整数線形計画問題と NC 同等であることを示した。つまり、どちらかの問題がNCに属するかP 完全であれば、もう一方も同様に同等である。^{[ 19 ]} NCにはNLが含まれるため、非決定性チューリングマシンであっても、GCD を計算するための空間効率の高いアルゴリズムが存在するかどうかもわかっていない。

この問題はNCでは解決されないことが知られていますが、ユークリッドの互除法よりも漸近的に高速な並列アルゴリズムが存在します。最も高速な決定論的アルゴリズムとして知られているのはChorとGoldreichによるもので、CRCW-PRAMモデルではn ^{1+ ε個の}プロセッサでO ( n /log n )時間で問題を解くことができます。 ^{[ 20 ]}ランダム化アルゴリズムでは、プロセッサ上でO ((log n ) ² )時間で問題を解くことができます（これは超多項式です）。^{[ 21 ]}${\displaystyle O\left(e^{\sqrt {n\log n}}\right)}$

プロパティ

• すべての正の整数aに対して、gcd( a , a ) = a です。
• aとbのすべての公約数はgcd( a , b )の約数です。
• gcd( a , b )（ただしaとbは共にゼロではない）は、d = a ⋅ p + b ⋅ q（ただしpとqは整数）の形で表される最小の正の整数dとして、代替的にかつ同値に定義されることもある。この式はベズーの恒等式と呼ばれる。このような数pとq は、拡張ユークリッド互除法によって計算できる。
• gcd( a , 0) = | a |、a ≠ 0の場合、任意の数は0の約数であり、aの最大約数は| a |であるため。^{[ 2 ] [ 5 ]}これは通常、ユークリッドの互除法の基本ケースとして使用されます。
• a が積b ⋅ cを割り切り、gcd( a、b ) = dである場合、a / d はcを割り切ります。
• mが正の整数の場合、 gcd( m ⋅ a , m ⋅ b ) = m ⋅gcd( a , b )となります。
• mが任意の整数の場合、 gcd( a + m ⋅ b , b ) = gcd( a , b )となります。同様に、gcd( a mod b , b ) = gcd( a , b )となります。
• mがaとbの正の公約数である場合、gcd( a / m、b / m ) = gcd( a、b )/ mとなります。
• gcd( a , b ) = d の場合、gcd( a / d , b / d ) = 1 となります。
• GCD は可換関数です: gcd( a , b ) = gcd( b , a )。
• GCDは結合関数です：gcd( a , gcd( b , c )) = gcd(gcd( a , b ), c )。したがって、gcd( a , b , c , ...)は複数の引数のGCDを表すために使用できます。
• GCD は次の意味で乗法関数です。a 1_とa ₂が互いに素であれば、gcd( a ₁ ⋅ a ₂ , b ) = gcd( a ₁ , b )⋅gcd( a ₂ , b )となります。
• gcd( a , b )は最小公倍数lcm( a , b )と密接に関係しており、

  gcd( a , b )⋅lcm( a , b ) = | a ⋅ b |。

この式は、最小公倍数を計算するためによく使用されます。まずユークリッドのアルゴリズムを使用して GCD を計算し、次に指定された数値の積を GCD で割ります。

• 分配性については次のバージョンが当てはまります。

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

  lcm( a、 gcd( b、c )) = gcd(lcm( a、b )、 lcm( a、c ))です。

• もし、 a = p ₁ ^{e ₁} p ₂ ^{e ₂} ⋅⋅⋅ p _m ^{e _m}とb = p ₁ ^{f ₁} p ₂ ^{f ₂} ⋅⋅⋅ p _m ^{f _m}（ただしe _i ≥ 0かつf _i ≥ 0）の一意の素因数分解がある場合、 aとbの GCDは

  gcd( a , b ) = p ₁ ^{min( e ₁ , f ₁ )} p ₂ ^{min( e ₂ , f ₂ )} ⋅⋅⋅ p _m ^{min( e _m , f _m )}。

• gcd(0, 0) = 0、lcm(0, 0) = 0と定義すると、自然数はGCDをmeet、LCMをjoin演算とする完全な分配格子になるため、便利な場合があります。 ^{[ 22 ]}この定義の拡張は、以下に示す可換環の一般化とも互換性があります。
• デカルト座標系では、gcd( a , b ) は、点(0, 0)と点( a , b )を結ぶ直線上の整数座標を持つ点間の線分の数として解釈できます。
• 非負整数aとb（ただしaとbは両方とも0ではない）は、 nを基数とするユークリッド互除法を考慮することで証明できる 。^{[ 23 ]}

  gcd( n ^a − 1, n ^b − 1) = n ^{gcd( a , b )} − 1。

• オイラーのトーティエント関数を含む恒等式：

  ${\displaystyle \gcd(a,b)=\sum _{k|a{\text{ and }}k|b}\varphi (k).}$

• GCD 合計関数（ピライの算術関数）:

${\displaystyle \sum _{k=1}^{n}\gcd(k,n)=\sum _{d|n}d\varphi \left({\frac {n}{d}}\right)=n\sum _{d|n}{\frac {\varphi (d)}{d}}=n\prod _{p|n}\left(1+\nu _{p}(n)\left(1-{\frac {1}{p}}\right)\right)}$ ここでp進評価です。（OEISのシーケンスA018804） ${\displaystyle \nu _{p}(n)}$

確率と期待値

1972年、ジェームズ・E・ナイマンは、 {1, ..., n }から独立かつ均一に選ばれたk個の整数は、 nが無限大に近づくにつれて確率1/ ζ ( k )で互いに素であることを示した。ここでζはリーマンゼータ関数を指す。^{[ 24 ]}（導出については「互いに素」を参照）。この結果は1987年に拡張され、 k個のランダムな整数が最大公約数dを持つ確率はd ^{− k} /ζ( k )であることが示された。^{[ 25 ]}

この情報を用いると、最大公約数関数の期待値は（非公式には） k = 2の場合には存在しないことがわかる。この場合、最大公約数がdに等しい確率はd ⁻² / ζ (2)なので、

${\displaystyle \mathrm {E} (\mathrm {2} )=\sum _{d=1}^{\infty }d(d^{-2}/\zeta (2))={\frac {1}{\zeta (2)}}\sum _{d=1}^{\infty }{\frac {1}{d}}.}$

この最後の和は調和級数であり、発散する。しかし、k ≥ 3の場合には期待値は明確に定義され、上記の議論によれば、

${\displaystyle \mathrm {E} (k)=\sum _{d=1}^{\infty }d^{1-k}\zeta (k)^{-1}={\frac {\zeta (k-1)}{\zeta (k)}}.}$

k = 3の場合、これは約1.3684に等しくなります。k = 4の場合、これは約1.1106になります。

可換環において

最大公約数の概念は、より一般的には任意の可換環の元に対して定義することができるが、一般には全ての元のペアに対して最大公約数が存在する必要はない。^{[ 26 ]}

• Rが可換環で、aとb がRに含まれる場合、 Rの元d は、 aとbの両方を割り切るとき、aとbの公約数と呼ばれます(つまり、Rにd · x  =  aかつd · y  =  bとなる元xとyがある場合)。
• d がaとbの公約数であり、 aとbのすべての公約数がd を割り切る場合、d はaとbの最大公約数と呼ばれます。

この定義によれば、2つの元aとbには複数の最大公約数が存在する可能性も、全く存在しない可能性もある。Rが整域である場合、 aとbの任意の2つの最大公約数は、定義によりどちらかが他方を割り切るため、必ず準元となる。実際、最大公約数が存在する場合、その準元のいずれか1つも最大公約数となる。

任意の整域において最大公約数（GCD）の存在は保証されない。しかし、Rが一意の因数分解域、あるいは他の任意のGCD 域 である場合、任意の2つの元は GCD を持つ。Rがユークリッド域であり、ユークリッド除算がアルゴリズム的に与えられる場合（例えば、R = F [ X ]でFが体 である場合、あるいはRがガウス整数環 である場合など）、除算手順に基づくユークリッド互除法の一種を用いて最大公約数を計算できる。

以下は、GCD を持たない 2 つの要素を持つ整数領域の例です。

${\displaystyle R=\mathbb {Z} \left[{\sqrt {-3}}\,\,\right],\quad a=4=2\cdot 2=\left(1+{\sqrt {-3}}\,\,\right)\left(1-{\sqrt {-3}}\,\,\right),\quad b=\left(1+{\sqrt {-3}}\,\,\right)\cdot 2.}$

要素2とは、 2 つの最大公約数です(つまり、 の倍数である任意の公約数は2に関連付けられており、についても同じことが当てはまりますが、これらは関連付けられていないため、 aと bの最大公約数は存在しません) 。 ${\displaystyle 1+{\sqrt {-3}}}$ ${\displaystyle 1+{\sqrt {-3}}}$

ベズー性質に対応して、任意の可換環において、 pa + qbの形式の元の集合を考えることができます。ここで、pとq は環全体にわたります。これはaとbによって生成されるイデアルであり、単に( a , b )と表記されます。すべてのイデアルが主である環 (主イデアル領域または PID) において、このイデアルは、ある環元dの倍数の集合と同一になります。この場合、このd はaとbの最大公約数です。しかし、イデアル( a , b )は、 aとbの最大公約数が存在しない場合でも役立ちます。(実際、エルンスト・クンマーは、フェルマーの最終定理を扱う際に、このイデアルを GCD の代わりとして使用しましたが、これをある仮想的な、またはイデアルな環元dの倍数の集合として想定しており、ここから環理論用語が生まれました。)

参照

• ベズードメイン
• 最小公分母
• ユニタリ除数

注記

1. ロング（1972年、33ページ）
2. ペットフレッツォ＆ビルキット（1970年、34ページ）
3. ケリー、W.マイケル (2004). 『代数学完全ガイド』ペンギン社. p. 142. ISBN 978-1-59257-161-1。。
4. ジョーンズ、アリン (1999). 『整数、小数、パーセンテージ、分数 7年生』 パスカル出版社. p. 16. ISBN 978-1-86441-378-6。。
5. ハーディ＆ライト（1979年、20頁）
6. 一部の著者は最大公約数と同義語として最大公約数を使用する。これは、使用されている単語の一般的な意味と矛盾しています。なぜなら、分母は分数を指し整数を掛け合わせることで、より大きな公約数が得られます）。
7. バーロウ、ピーター；ピーコック、ジョージ；ラードナー、ディオニシウス；エアリー、サー・ジョージ・ビデル；ハミルトン、H.P .；レヴィ、A.；ド・モーガン、オーガスタス；モズレー、ヘンリー (1847). 『純粋数学百科事典』 R. グリフィン社 p. 589.。
8. 一部の著者は( a , b )を使用するが、 ^{[ 1 ] [ 2 ] [ 5 ]}、この表記はしばしば曖昧である。Andrews (1994 , p. 16) はこれを次のように説明している。「多くの著者はgcd ( a , b )を ( a , b )と。我々はそうしない。なぜなら、ユークリッド平面上の点を表すには( a , b )をしばしば使用するからである。」
9. Thomas H. Cormen他著『アルゴリズム入門』（第2版、2001年） ISBN 0262032937、852ページ
10. バーナード・L・ジョンストン、フレッド・リッチマン著『数と対称性：代数学入門』ISBN 084930301X、38ページ
11. マーティン・R・ディクソン他著『代数的構造入門』ISBN 1118497759、59ページ
12. 例えば、 Wolfram Alpha計算とMaxima
13. ジョナサン・カッツ、イェフダ・リンデル著『現代暗号入門』ISBN 1351133012、2020年、セクション9.1.1、p.45
14. Weisstein, Eric W. 「最大公約数」 . mathworld.wolfram.com . 2020年8月30日閲覧。
15. 「最大公約数」www.mathsisfun.com . 2020年8月30日閲覧。
16. Slavin, Keith R. (2008). 「Q-二項式と最大公約数」 . INTEGERS: The Electronic Journal of Combinatorial Number Theory . 8.ウェストジョージア大学、プラハ・チャールズ大学: A5 . 2008年5月26日閲覧。
17. Schramm, Wolfgang (2008). 「最大公約数関数のフーリエ変換」 . INTEGERS: The Electronic Journal of Combinatorial Number Theory . 8.西ジョージア大学、プラハ・チャールズ大学: A50 . 2008年11月25日閲覧。
18. Knuth, Donald E. (1997). 『コンピュータプログラミングの芸術』第2巻：半数値アルゴリズム（第3版）. Addison-Wesley Professional. ISBN 0-201-89684-2。
19. Shallcross, D.; Pan, V.; Lin-Kriz, Y. (1993). 「平面整数線形計画法とユークリッドGCDのNC同値性」(PDF) . 34th IEEE Symp. Foundations of Computer Science . pp.  557– 564. 2006年9月5日時点のオリジナルよりアーカイブ(PDF) 。
20. Chor, B. ; Goldreich, O. (1990). 「整数GCDのための改良並列アルゴリズム」. Algorithmica . 5 ( 1–4 ): 1–10 . doi : 10.1007/BF01840374 . S2CID 17699330 . 
21. Adleman, LM; Kompella, K. (1988). 「平滑性を用いた並列処理の実現」.第20回ACMコンピューティング理論シンポジウム. ニューヨーク. pp.  528– 538. doi : 10.1145/62212.62264 . ISBN 0-89791-264-0. S2CID  9118047 .
22. ミュラー＝ホイッセン、フォルケルト;ヴァルター、ハンス・オットー (2012)。 「ドブ・タマリ（元ベルンハルト・タイトラー）」。ミュラー・ホイッセン、フォルケルトにて。パロ、ジャン・マルセル。スタシェフ、ジム(編)。アソシヘドラ、タマリ格子および関連構造物: タマリ記念祭典。数学の進歩。 Vol. 299.ビルクホイザー。1 ～ 40ページ 。ISBN 978-3-0348-0405-9。脚注27、9ページ：「例えば、gcd（最大公約数）をmeet、lcm（最小公倍数）をjoin演算とする自然数は、（完全分配）格子を決定する。」この結果を得るには、0に関するこれらの定義を含める必要がある。自然数の集合から0を省略すると、結果として得られる格子は完全ではない。
23. ドナルド・E. クヌース、RL グラハム、O. パタシュニク（1994年3月）『具体的な数学：コンピュータサイエンスの基礎』アディソン・ウェズリー、ISBN 0-201-55802-5。
24. Nymann, JE (1972). 「 k個の正整数が互いに素である確率について」 .整数論ジャーナル. 4 (5): 469– 473. Bibcode : 1972JNT.....4..469N . doi : 10.1016/0022-314X(72)90038-8 .
25. Chidambaraswamy, J.; Sitarmachandrarao, R. (1987). 「 m個の多項式の値が与えられた最大公約数を持つ確率について」Journal of Number Theory . 26 (3): 237– 245. doi : 10.1016/0022-314X(87)90081-3 .
26. Lovett, Stephen (2015). 「可換環における分割可能性」.抽象代数：構造と応用. ボカラトン: CRC Press. pp.  267– 318. ISBN 9781482248913。

参考文献

• アンドリュース、ジョージ・E. (1994) [1971].数論. ドーバー. ISBN 978-0-486-68252-5。
• ハーディ, GH ;ライト, EM (1979). 『数論入門』（第5版）. オックスフォード:オックスフォード大学出版局. ISBN 978-0-19-853171-5。
• ロング、カルビン・T. (1972).初等数論入門（第2版）. レキシントン: DC Heath and Company . LCCN  77171950 .
• ペットフレッツォ, アンソニー J.; バーキット, ドナルド R. (1970). 『数論の原論』 エングルウッド・クリフス:プレンティス・ホール. LCCN  71081766 .

さらに読む

• ドナルド・クヌース著『コンピュータプログラミングの技法』第2巻：半数値アルゴリズム、第3版、アディソン・ウェスレー、1997年、ISBN 0-201-89684-2セクション4.5.2: 最大公約数、333～356ページ。
• Thomas H. Cormen 、 Charles E. Leiserson、Ronald L. Rivest、Clifford Stein著『アルゴリズム入門第2版』MIT Press and McGraw-Hill、2001年。ISBN 0-262-03293-7セクション31.2: 最大公約数、856～862ページ。
• サンダース・マクレーンとギャレット・バーコフ著『現代代数学概論』第4版、マクミラン出版、1977年、ISBN 0-02-310070-21～7：「ユークリッドの互除法」

外部リンク

• gcd(x,y) = y 関数グラフ: https://www.desmos.com/calculator/6nizzenog5