最大公約数

数学において、すべてゼロではない2 つ以上の整数の最大公約数( GCD )は、最大公約数 ( GCF )とも呼ばれ、各整数を割り切る最大の正の整数です。2 つの整数 $x$ 、 $yの場合、$ $x$ と $y$ の最大公約数はと表されます。たとえば、8 と 12 の GCD は 4 です。つまり、 $gcd(8, 12) = 4$ です。^[1]^[2] $\gcd(x,y)$

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

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

概要

意味

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

$a$ と $b$ のいずれかがゼロの場合、GCD はゼロ以外の整数の絶対値です: $gcd(a, 0) = gcd(0, a) = | a |$ 。このケースは、ユークリッドのアルゴリズムの終了ステップとして重要です。

上記の定義は $gcd(0, 0) を定義するのには不適切です。なぜなら$ $0 \times$ $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 つの整数の積としていくつかの方法で表現できます。

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 の共通約数です。

1,2,3,6.

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

\gcd(54,24)=6.

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

互いに素な数

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

幾何学的な視点

「縦に長い長方形が正方形の格子に分割されています。長方形の幅は 2 正方形、高さは 5 正方形です。」 — 24 x 60 の長方形は、12 x 12 の正方形タイル 10 枚で覆われます。ここで、12 は 24 と 60 の最大公約数です。より一般的には、cがaとbの公約数である場合にのみ、a x *bの長方形は、辺の長さがc の*正方形タイルで覆われます。

たとえば、24 x 60 の長方形領域は、1 x 1 の正方形、2 x 2 の正方形、3 x 3 の正方形、4 x 4 の正方形、6 x 6 の正方形、または 12 x 12 の正方形のグリッドに分割できます。したがって、12 は 24 と 60 の最大公約数です。したがって、24 x 60 の長方形領域は、12 x 12 の正方形のグリッドに分割でき、一方の辺に 2 つの正方形 ( $24/12 = 2$ )、もう一方の辺に 5 つの正方形 ( $60/12 = 5$ ) が配置されます。

アプリケーション

分数の縮約

最大公約数は分数を最小の項に縮めるのに便利です。^[15]たとえば、 $gcd(42, 56) = 14$ なので、

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

最小公倍数

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

\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)$ を計算するには、次のようにします。

{\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)を計算する場合、計算は次のようになります。

{\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 アルゴリズムは、ほとんどのコンピューターで使用されている数値のバイナリ表現に特別に適応されたユークリッドのアルゴリズムのバリエーションです。

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

方法は、 GCD を求める 2 つの正の整数 $a$ と $bから開始します。$

$a$ と $b$ が両方とも偶数の場合、少なくともどちらかが奇数になるまで両方を 2 で割ります。この割り算のペアの数を $dとします。$
$a$ が偶数の場合は、奇数になるまで 2 で割ります。
$b$ が偶数の場合は、奇数になるまで 2 で割ります。
ここで、 $a$ と $bは$ 両方とも奇数であり、計算の最後まで奇数のままである。
a ≠ bの場合
- $a > b$ の場合、 $a を$ $a - b$ に置き換え、その結果を 2 で割り、 $a が$ 奇数になるまで続けます ( $a$ と $b は$ 両方とも奇数なので、少なくとも 1 回は 2 で割ります)。
- $a < b$ の場合は、 $b を$ $b - a$ に置き換え、 $b が$ 奇数になるまでその結果を 2 で割ります。
ここで、 $a = b で$ あり、最大公約数は $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 1$ と $a = b = 3$ の積 6 になります。

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

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

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

計算の複雑さは通常、入力の長さ $n$ で表されます。ここでは、この長さは $n = log a + log b$ であり、計算の複雑さは次のように表されます。

O(n^{2})

。

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

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

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

その他の方法

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

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

、

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

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

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

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

キース・スラヴィンは奇数 $a \geq 1$ に対して次のことを示しました。

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

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

\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 (n2)$ である。これは $、$ 最大公約数の計算が、定数倍まで、乗算と同じ複雑さを持つことを意味する。

ただし、高速乗算アルゴリズムを使用する場合、ユークリッドのアルゴリズムを修正して複雑さを改善できますが、最大公約数の計算は乗算よりも遅くなります。より正確には、 $nビットの 2 つの整数の乗算に$ $T (n)$ の時間がかかる場合、最大公約数を求める最も高速な既知のアルゴリズムの複雑さは $O (T (n) log n)です。これは、最も高速な既知のアルゴリズムの複雑さが$ $O (n (log n) 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$ $)$ $2$ $)$ 時間で問題を解くことができます(これは超多項式です)。^[21] $\exp \left(O\left({\sqrt {n\log n}}\right)\right)$

プロパティ

正の整数 $a$ の場合、 $gcd(a, a) = a$ です。
$a$ と $b$ のすべての公約数は $gcd(a, b)$ の約数です。
$gcd(a, b) （$ aとb は両方ともゼロではない）は、 $d$ $=$ $a$ $\cdot$ $p$ $+$ $b$ $\cdot$ $q$ （pとqは整数）の形式で表すことができる最小の正の整数dとして、代替的にかつ同等に定義されることもあります。この式はベズーの恒等式と呼ばれます。このような数pとq は、拡張ユークリッド互除法で計算できます。
$gcd(a, 0) = | a |$ 、 $a \neq 0$ の場合、任意の数は0の約数であり、aの最大約数は $| a |$ であるため。^[2]^[5] これは通常、ユークリッドの互除法の基本ケースとして使用されます。
a が積b ⋅ c を割り切る場合、 $gcd(a, b) = d$ であれば、a / d はc を割り切れます。
mが正の整数の場合、 $gcd(m \cdot a, m \cdot b) = m \cdotgcd(a, b)$ となります。
mが任意の整数の場合、 $gcd(a + m \cdot 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 は可換関数です: $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$ ₁ $\cdot$ $a$ $2$ $,$ $b$ $) = gcd($ $a$ $1$ $,$ $b$ $)\cdotgcd($ $a$ $2$ $,$ $b$ $)$ となります。
$gcd(a, b)は$ 最小公倍数 $lcm(a, b)$ と密接に関係しており、
$gcd(a, b)\cdotlcm(a, b) = | a \cdot 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 1 e 1 p 2 e 2 \cdot\cdot\cdot p m e m$ と $b = p 1 f 1 p 2 f 2 \cdot\cdot\cdot p m f m$ （ $e i \geq 0$ 、 $f i \geq 0 ）$ の一意の素因数分解がある場合、 aとbの GCDは
$gcd(a, b) = p 1 min(e 1, f 1) p 2 min(e 2, f 2) \cdot\cdot\cdot 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は$ 両方ともゼロではない）は、 nを基数とするユークリッド互除法を考えることによって証明できる：^[23]
$gcd(n a - 1, n b - 1) = n gcd(a, b) - 1$ 。
オイラーのトーティエント関数を含む恒等式:
$\gcd(a,b)=\sum _{k|a{\text{ and }}k|b}\varphi (k).$
GCD 総括関数（ピライの算術関数）：

$\sum _{k=1}^{n}\gcd(k,n)=\sum _{d|n}d\phi \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 ) $\nu _{p}(n)$

確率と期待値

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

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

\mathrm {E} (\mathrm {2} )=\sum _{d=1}^{\infty }d{\frac {6}{\pi ^{2}d^{2}}}={\frac {6}{\pi ^{2}}}\sum _{d=1}^{\infty }{\frac {1}{d}}.

この最後の和は調和級数であり、発散する。しかし、 $k \geq 3 の$ とき、期待値は明確に定義されており、上記の議論によれば、

\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 つの GCD は、定義によりいずれかが他方を割り切るため、$ 関連要素である必要があります。実際、GCD が存在する場合、その関連要素のいずれか 1 つも GCD です。

GCD の存在は、任意の整域では保証されません。ただし、 $R が$ 一意の因数分解領域またはその他のGCD 領域である場合、任意の 2 つの要素は GCD を持ちます。R がユークリッド領域であり、ユークリッド除算がアルゴリズム的に与えられる場合 $($ たとえば、R = F [ X ] で F が体である場合 $、または R がガウス整数$ の $環$ である場合など $)$ 、除算手順に基づくユークリッドのアルゴリズムの形式を使用して最大公約数を計算できます。

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

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

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

参照

注記

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

さらに読む

ドナルド・クヌース。『コンピュータプログラミングの芸術』第2巻：半数値アルゴリズム、第3版。Addison-Wesley、1997年。ISBN 0-201-89684-2。セクション4.5.2：最大公約数、pp. 333–356 。
Thomas H. Cormen、Charles E. Leiserson、Ronald L. Rivest、Clifford Stein。アルゴリズム入門、第 2 版。MIT Press および McGraw-Hill、2001 年。ISBN 0-262-03293-7。セクション 31.2: 最大公約数、pp. 856–862 。
Saunders Mac LaneおよびGarrett Birkhoff。「現代代数学の概観」、第 4 版。MacMillan Publishing Co.、1977 年。ISBN 0-02-310070-2。1～ 7:「ユークリッドの互除法」。

[Long_1972_33-1] Long (1972, p. 33)

[Pettofrezzo_1970_34-2] ペットフレッツォ＆ビルキット（1970年、34ページ）

[3] ケリー、W.マイケル（2004）。『代数学完全ガイド』ペンギン社、142ページ。ISBN 978-1-59257-161-1。。

[4] ジョーンズ、アリン（1999）。整数、小数、パーセンテージ、分数7年生。パスカルプレス。p.16。ISBN 978-1-86441-378-6。。

[Hardy&Wright_1979_20-5] ハーディ＆ライト（1979年、20ページ）

[6] 一部の著者は最大公約数と同義である最大公約数。これは、使用されている単語の一般的な意味と矛盾しています。 分母は分数を指し、2 つの分数には最大公約数が存在しないからです (2 つの分数が同一の分母を持つ場合、すべての分子と分母に同一の整数を掛け合わせることで、より大きな公約数が得られます)。

[7] バーロウ、ピーター;ピーコック、ジョージ;ラードナー、ディオニシウス;エアリー、サー・ジョージ・ビデル;ハミルトン、H.P . ; レヴィ、A. ;ド・モルガン、オーガスタス; モズレー、ヘンリー (1847)。純粋数学百科事典。R. グリフィン社、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、p. 852

[10] バーナード・L・ジョンストン、フレッド・リッチマン『数と対称性：代数学入門』 ISBN 084930301X、38ページ

[11] Martyn R. Dixon他著『基本的な代数構造入門』 ISBN 1118497759、p. 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: 組合せ数論の電子ジャーナル. 8.ウェストジョージア大学、プラハ・チャールズ大学: A5 . 2008年5月26日閲覧。

[17] ^ Schramm, Wolfgang ( 2008). 「最大公約数の関数のフーリエ変換」. INTEGERS: 組合せ数論の電子ジャーナル. 8.ウェストジョージア大学、プラハ・チャールズ大学: A50 . 2008年11月25日閲覧。

[18] Knuth, Donald E. (1997). The Art of Computer Programming . 第 2 巻: Seminumerical Algorithms (第 3 版). Addison-Wesley Professional. ISBN 0-201-89684-2。

[19] Shallcross, D.; Pan, V.; Lin-Kriz, Y. (1993). 「平面整数線形計画法とユークリッド GCD の NC 等価性」(PDF)。第 34 回 IEEE シンポジウム。コンピュータサイエンスの基礎。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。

[nymann-24] Nymann, JE (1972). 「k個の正の整数が互いに素である確率について」.数論ジャーナル. 4 (5): 469–473. Bibcode :1972JNT.....4..469N. doi : 10.1016/0022-314X(72)90038-8 .

[chid-25] Chidambaraswamy, J.; Sitarmachandrarao, R. (1987). 「m 個の多項式の値が与えられた gcd を持つ確率について」Journal of Number Theory . 26 (3): 237–245. doi : 10.1016/0022-314X(87)90081-3 .

[26] Lovett, Stephen (2015). 「可換環における分割可能性」。抽象代数：構造と応用。ボカラトン：CRC プレス。pp. 267–318。ISBN 9781482248913。