最大公約数

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

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

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

概要

意味

少なくとも一方がゼロでない整数 $a$ と $b$ の最大公約数(GCD) は、 $a$ と $b$ の両方の約数となる最大の正の整数 $dです$ $。$ つまり、 $a$ $=$ $de$ かつ $b$ $=$ $df$ となる整数 $e$ と $f$ が存在し、 $d は$ そのような最大の整数です。aと $b$ の最大公約数は一般に $gcd($ $a$ $,$ $b$ $)$ $と$ 表記されます。^[⁸^]

$a$ と $b$ のどちらかがゼロの場合、最大公約数はゼロでない整数の絶対値になります。gcd $(a, 0) = gcd(0, a) = | a |$ 。このケースは、ユークリッドの互除法の終了ステップとして重要です。

上記の定義は、 $0 \times$ $n$ $= 0$ となる最大の整数 $n が$ 存在しないため、 $gcd(0, 0) を定義するのには不適切です。しかし、$ 最大が割り切れる関係の文脈で理解される場合、ゼロはそれ自身の最大の約数であるため、 $gcd(0, 0)$ は一般的に $0$ と定義されます。これにより、GCD の通常の恒等式、特にベズーの恒等式、すなわち $gcd($ $a$ $,$ $b$ $)が$ ${$ $a$ $,$ $b$ $}$ と同じイデアルを生成するという恒等式が維持されます。^[⁹^]^[¹⁰^]^[¹¹^]この慣例は、多くのコンピュータ代数システムで採用されています。^[¹²^]それにもかかわらず、一部の著者は $gcd(0, 0)$ を未定義のままにしています。^[¹³^]

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

例

数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なので、6が最大公約数です。

\gcd(54,24)=6.

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

互いに素な数

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

幾何学的視点

「縦長で細長い長方形が、正方形の格子状に区切られている。長方形の幅は2マス、高さは5マスである。」 — 24×60の長方形は、12×12の正方形タイル10枚で覆われます。ここで、12は24と60の最大公約数です。より一般的には、a × bの長方形は、cがaとbの公約数である場合に限り、辺の長さがcの正方形タイルで覆うことができます。

例えば、24×60の長方形の領域は、1×1の正方形、2×2の正方形、3×3の正方形、4×4の正方形、6×6の正方形、または12×12の正方形のグリッドに分割できます。したがって、12は24と60の最大公約数です。このように、24×60の長方形の領域は、1辺に2つの正方形（ $24/12 = 2$ ）、もう一方の辺に5つの正方形（ $60/12 = 5$ ）がある12×12の正方形のグリッドに分割できます。

アプリケーション

分数の約分

最大公約数は、分数を既約分数にするために役立ちます。^{[ 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 ¹を見つけます。すると、最大公約数は 2 ^min(4,2) · 3 ^min(1,2) · 5 ^min(0,1) = 2 ² · 3 ¹ · 5 ⁰ = 12 となります。対応する最小公倍数は、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つの数の差に置き換え、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アルゴリズム

二進数最大公約数アルゴリズムは、ユークリッドの互除法の変形であり、ほとんどのコンピュータで使用されている数値の二進数表現に特化して調整されています。

二進数の最大公約数アルゴリズムは、計算中に遭遇する偶数を毎回2で割るという点で、ユークリッドの互除法と本質的に異なります。その効率性は、二進数表現では偶奇性の判定が最右端の桁の判定に相当し、2で割る操作が最右端の桁の除去に相当するという事実に基づいています。

その方法は以下のとおりで、まず最大公約数を求める2つの正の整数 $a$ と $bから始めます。$

$a$ と $b$ が両方とも偶数の場合、少なくともどちらか一方が奇数になるまで両方を2で割ります。d $を$ このペアになった割り算の回数とします。
$a$ が偶数の場合は、奇数になるまで2で割ります。
$b$ が偶数の場合は、奇数になるまで2で割ります。
ここで、 $a$ と $bは$ どちらも奇数であり、計算が終わるまで奇数のままです。
a ≠ bの間は
- $a > b$ の場合、 $a を$ $a - b$ に置き換え、 $a が$ 奇数になるまで結果を 2 で割ります( $a$ と $b$ は両方とも奇数なので、少なくとも 1 回は 2 で割ります)。
- $a < b$ の場合、 $b を$ $b - a$ に置き換え、 $b が$ 奇数になるまで結果を 2 で割ります。
ここで、 $a = b$ であり、最大公約数は $2da.$

ステップ1では、 $a$ と $b$ を割り切る $2$ のべき乗の最大値、つまり最大公約数として $dを決定します。どのステップでも、$ $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) ; 元の最大公約数は、6 と $2 d = 2 1$ および $a = b = 3 の$ 積です。

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

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

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

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

O(n^{2})

。

レーマーの最大公約数アルゴリズム

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

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

その他の方法

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

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

、

しかし、より一般的には、最小公倍数は最大公約数から計算されます。

トーマエの関数 $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}}

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

複雑

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

しかし、高速な乗算アルゴリズムを使用する場合、複雑性を改善するためにユークリッドアルゴリズムを修正することはできますが、最大公約数の計算は乗算よりも遅くなります。より正確には、 $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 完全であれば、もう一方の問題も同様である。^[¹⁹^] NCにはNLが含まれているため、非決定性チューリングマシンであっても、GCD を計算するためのスペース効率の良いアルゴリズムが存在するかどうかも不明である。

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

不動産

すべての正の整数 $a$ に対して、 $gcd(a, a) = a$ 。
$a$ と $b$ のすべての公約数は $gcd(a, b)$ の約数である。
aとb が両方ともゼロではない場合の $gcd($ $a$ $,$ $b$ $)$ は、代わりに、 $d$ $=$ $a$ $\cdot$ $p$ $+$ $b$ $\cdot$ $q$ の形で表せる最小の正の整数dとして定義することもできます。ここで、pとqは整数です。この式はベズーの恒等式と呼ばれます。このような数pとq は、拡張ユークリッド互除法で計算できます。
$a \neq 0$ の場合、 $gcd($ $a$ $, 0) =$ $|$ $a$ $|$ となります。これは、任意の数が 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(a, b) = d の$ 場合、 $gcd(a / d, b / d) = 1 となり$ ます。
最大公約数は可換関数です: $gcd(a, b) = gcd(b, a)$ 。
最大公約数は結合法則を満たす関数です。gcd $(a, gcd(b, c)) = gcd(gcd(a, b), c)$ 。したがって、 $gcd(a, b, c, ...)$ は複数の引数の最大公約数を表すために使用できます。
最大公約数は、次の意味で乗法関数です $。a$ 1 と a 2 が互いに素である場合、gcd ( a ₁ ⋅ $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(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 pm e m$ および $b = p 1 f 1 p 2 f 2 \cdot\cdot\cdot pm f m$ という一意の素因数分解があり、 $e$ $i \geq 0$ および $f i \geq 0$ $で$ ある場合、 aとbの最大公約数は
$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 を交点、LCM を結合演算とする完全な分配束になるので、便利な場合がある。 ^{[ 22 ]}この定義の拡張は、以下に示す可換環の一般化とも互換性がある。
デカルト座標系では、 $gcd(a, b) は$ 、点 $(0, 0)$ と $($ $a$ $,$ $b$ $)を結ぶ直線$ セグメント上の整数座標を持つ点間のセグメントの数として解釈できます。
非負整数 $a$ と $b$ に対して、 $a$ と $b が$ 両方ともゼロでない場合、n を基数とするユークリッドアルゴリズムを考慮することで証明できます。^[²³^]
$gcd(n a - 1, n b - 1) = n gcd(a, b) - 1$ 。
オイラーのトーシェント関数に関する恒等式：
$\gcd(a,b)=\sum _{k|a{\text{ および }}k|b}\varphi (k).$
最大公約数の総和関数（ピライの算術関数）：

$\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)$ どこ $\nu _{p}(n)$ $これはp$ 進評価です。（OEISのシーケンスA018804）

確率と期待値

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

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

\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 \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$ の両方を割り切る場合(つまり、d · x = aかつd · y = bとなるような要素 $x$ と $yが$ $R$ に存在する場合) は、 $a$ と $b$ の共通因子と呼ばれます。
$d が$ $a$ と $b$ の公約数であり、 $a$ と $b$ のすべての公約数が $d を$ 割り切る場合、 $d は$ $a$ とbの最大公約数と呼ばれます。

この定義によれば、2つの要素 $a$ と $bは、$ 複数の最大公約数を持つ場合もあれば、全く持たない場合もある。Rが整域である場合 $、$ aと $b$ の $任意$ の2つの最大公約数は、定義上、どちらか一方が他方を割り切るため、必ず関連要素となる。実際、最大公約数が存在する場合、その関連要素の1つもまた最大公約数となる。

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

以下は、最大公約数を持たない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$ の最大公約数は存在しません。

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

注記

1 2ロング（1972年、33ページ）
1 2 3 Pettofrezzo & Byrkit (1970 、p. 34)
↑ケリー、W. マイケル (2004)。『代数学完全入門』ペンギン社。142ページ。ISBN 978-1-59257-161-1。。
↑ジョーンズ、アリン (1999).整数、小数、パーセンテージ、分数 7 年生. パスカルプレス. p. 16. ISBN 978-1-86441-378-6。。
1 2 3ハーディ＆ライト（1979年、20ページ）
↑一部の著者は最大公約数と最大公約数を同義語として用いるのは誤りです。分母は分数を指す整数を掛けることで、より大きな公約数が得られます）。
↑バーロウ、ピーター;ピーコック、ジョージ;ラードナー、ディオニュシウス;エアリー、サー・ジョージ・ビデル;ハミルトン、HP ; レヴィ、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、852ページ
↑バーナード・L・ジョンストン、フレッド・リッチマン著『数と対称性：代数学入門』ISBN 084930301X38ページ
↑ Martyn R. Dixon他著、『 An Introduction to Essential Algebraic Structures 』ISBN 1118497759、59ページ
↑例： Wolfram Alphaの計算とMaxima
↑ジョナサン・カッツ、イェフダ・リンデル著『現代暗号入門』ISBN 13511330122020年、第9.1.1項、45ページ
↑ Weisstein, Eric W. 「最大公約数」 . mathworld.wolfram.com . 2020年8月30日取得。
↑ 「最大公約数」。www.mathsisfun.com 。 2020年8月30日取得。
↑ Slavin, Keith R. (2008). "Q-二項式と最大公約数" . INTEGERS: The Electronic Journal of Combinatorial Number Theory . 8. University of West Georgia , Charles University in Prague : A5 . 2008年5月26日取得。
↑ Schramm, Wolfgang (2008). "最大公約数の関数のフーリエ変換" . INTEGERS: The Electronic Journal of Combinatorial Number Theory . 8 . University of West Georgia , Charles University in Prague : A50 . 2008-11-25に取得.
↑クヌース、ドナルド・E. (1997).コンピュータプログラミングの技法第2巻：半数値アルゴリズム（第3版）. Addison-Wesley Professional. ISBN 0-201-89684-2。
↑ Shallcross, D.; Pan, V.; Lin-Kriz, Y. (1993). "平面整数線形計画法とユークリッド最大公約数のNC等価性" (PDF) .第34回IEEEシンポジウム「コンピュータサイエンスの基礎」 . pp. 557–564 . 2006年9月5日にオリジナルからアーカイブされた(PDF) 。
↑ Chor, B. ; Goldreich, O. (1990). "整数の最大公約数を求めるための改良された並列アルゴリズム". 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 ）を交点、最小公倍数（ lcm）を結合演算とする自然数は、（完全な分配）格子を決定します。」この結果を得るには、0に関するこれらの定義を含める必要があります。代わりに自然数の集合から0を除外すると、結果として得られる格子は完全ではありません。
↑クヌース、ドナルド・E. ;グラハム、RL ; パタシュニク、O. (1994 年 3 月).具体的な数学: コンピュータ科学の基礎.アディソン・ウェスリー. ISBN 0-201-55802-5。
↑ Nymann, JE (1972). " $k$ 個の正の整数が互いに素である確率について" . Journal of Number Theory . 4 (5): 469– 473. Bibcode : 1972JNT.....4..469N . doi : 10.1016/0022-314X(72)90038-8 .
↑ Chidambaraswamy, J.; Sitarmachandrarao, R. (1987). "On the probability that the values of m polynomials have a given gcd" Journal of Number Theory . 26 (3): 237– 245. doi : 10.1016/0022-314X(87)90081-3 .
↑ロベット、スティーブン（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。
Long, Calvin T. (1972).数論入門（第2 版）. レキシントン：DC Heath and Company . LCCN 77171950 .
Pettofrezzo, Anthony J.; Byrkit, Donald R. (1970).数論の基礎. Englewood Cliffs: Prentice Hall . 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およびMcGraw-Hill、2001年。ISBN 0-262-03293-7セクション 31.2: 最大公約数、pp. 856–862。
サンダース・マックレーン、ギャレット・バーコフ著『現代代数学概論』第4版、マクミラン出版、1977年。ISBN 0-02-310070-21～7：「ユークリッドの互除法」

外部リンク

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

[Long_1972_33-1] 1 2ロング（1972年、33ページ）

[Pettofrezzo_1970_34-2] 1 2 3 Pettofrezzo & Byrkit (1970 、p. 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] 1 2 3ハーディ＆ライト（1979年、20ページ）

[6] 一部の著者は最大公約数と最大公約数を同義語として用いるのは誤りです。分母は分数を指す整数を掛けることで、より大きな公約数が得られます）。

[7] バーロウ、ピーター;ピーコック、ジョージ;ラードナー、ディオニュシウス;エアリー、サー・ジョージ・ビデル;ハミルトン、HP ; レヴィ、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、852ページ

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

[11] Martyn R. Dixon他著、『 An Introduction to Essential Algebraic Structures 』ISBN 1118497759、59ページ

[12] 例： Wolfram Alphaの計算とMaxima

[13] ジョナサン・カッツ、イェフダ・リンデル著『現代暗号入門』ISBN 13511330122020年、第9.1.1項、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. University of West Georgia , Charles University in Prague : A5 . 2008年5月26日取得。

[17] Schramm, Wolfgang (2008). "最大公約数の関数のフーリエ変換" . INTEGERS: The Electronic Journal of Combinatorial Number Theory . 8 . University of West Georgia , Charles University in Prague : A50 . 2008-11-25に取得.

[18] クヌース、ドナルド・E. (1997).コンピュータプログラミングの技法第2巻：半数値アルゴリズム（第3版）. Addison-Wesley Professional. ISBN 0-201-89684-2。

[19] Shallcross, D.; Pan, V.; Lin-Kriz, Y. (1993). "平面整数線形計画法とユークリッド最大公約数のNC等価性" (PDF) .第34回IEEEシンポジウム「コンピュータサイエンスの基礎」 . pp. 557–564 . 2006年9月5日にオリジナルからアーカイブされた(PDF) 。

[20] Chor, B. ; Goldreich, O. (1990). "整数の最大公約数を求めるための改良された並列アルゴリズム". 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 ）を交点、最小公倍数（ lcm）を結合演算とする自然数は、（完全な分配）格子を決定します。」この結果を得るには、0に関するこれらの定義を含める必要があります。代わりに自然数の集合から0を除外すると、結果として得られる格子は完全ではありません。

[23] クヌース、ドナルド・E. ;グラハム、RL ; パタシュニク、O. (1994 年 3 月).具体的な数学: コンピュータ科学の基礎.アディソン・ウェスリー. ISBN 0-201-55802-5。

[nymann-24] Nymann, JE (1972). " $k$ 個の正の整数が互いに素である確率について" . Journal of Number Theory . 4 (5): 469– 473. Bibcode : 1972JNT.....4..469N . doi : 10.1016/0022-314X(72)90038-8 .

[chid-25] Chidambaraswamy, J.; Sitarmachandrarao, R. (1987). "On the probability that the values of m polynomials have a given gcd" Journal of Number Theory . 26 (3): 237– 245. doi : 10.1016/0022-314X(87)90081-3 .

[26] ロベット、スティーブン（2015）。「可換環における可除性」。抽象代数学：構造と応用。ボカラトン：CRC Press。pp. 267–318。ISBN 9781482248913。

[ 1 ]

[ 2 ]

。[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[

[

[

[

[

[

[

[ 15 ]

[ 16 ]

[

]ユークリッドの互除法と

[

[

[ 21 ]

[ 22 ]

[

[

[

[ 26 ]

最大公約数

概要

意味

例

互いに素な数

幾何学的視点

アプリケーション

分数の約分

最小公倍数

計算

素因数分解を用いる

ユークリッドの互除法

ユークリッドの互除法

バイナリGCDアルゴリズム

レーマーの最大公約数アルゴリズム

その他の方法

複雑

不動産

確率と期待値

可換環において

関連項目

注記

参考文献

さらに読む

外部リンク

関連するトピック

数学

整数

を割り切る最大の正の整数です。2 つの整数

この概念は多項式（多項式の最大公約数