最大公約数

最大公約数（さいだいこうやくすう、英: greatest common divisor^{[注釈 1]}）とは、すべての公約数を約数にもつ公約数である。特に正の整数では、最大公約数は通常の大小関係についての最大の公約数と一致し、その存在性はユークリッドの互除法により保証される。

自然数の整除関係を図示した無限グラフ（ハッセ図）の一部。たとえば8と12の最大公約数は4であり、4と6の最大公約数は2である。

初等的な定義

以下では、自然数は ${\displaystyle 0}$ を含むとし、${\displaystyle a}$ が ${\displaystyle b}$ を割り切ること（つまり ${\displaystyle b=ca}$ となる自然数 ${\displaystyle c}$ が存在すること）を ${\displaystyle a\mid b}$ と表す。

写像 ${\displaystyle \gcd \colon \mathbb {N} ^{n}\to \mathbb {N}$ ;(a_{1},\dots ,a_{n})\mapsto d} を

1. すべての ${\displaystyle 1\leqq i\leqq n}$ に対して ${\displaystyle d\mid a_{i}}$ であり、
2. すべての自然数 ${\displaystyle b}$ に対し、すべての ${\displaystyle 1\leqq i\leqq n}$ に対して ${\displaystyle b\mid a_{i}}$ ならば ${\displaystyle b\mid d}$ となる

ように定める^[1][2][3][4]。${\displaystyle d}$ を ${\displaystyle a_{1},\dots ,a_{n}}$ の最大公約数といい、${\displaystyle \gcd(a_{1},\dots ,a_{n})}$ や ${\displaystyle (a_{1},\dots ,a_{n})}$ と表す。${\displaystyle \gcd(a_{1},\dots ,a_{n})=1}$ が成り立つことを ${\displaystyle a_{1},\dots ,a_{n}}$ が互いに素であると言う。

この定義から容易に次のことがわかる。

• ${\displaystyle \gcd(a,b)=\gcd(b,a)}$ が成り立つ。
• ${\displaystyle \gcd(\gcd(a,b),c)=\gcd(a,\gcd(b,c))=\gcd(a,b,c)}$ が成り立つ^[2]。
• 最大公約数は存在すれば一意である^[5]。
• ${\displaystyle n=0}$ であれば（つまり空集合の）最大公約数は ${\displaystyle 0}$ である^[2]。空積が ${\displaystyle 1=\{\varnothing \}}$ であることと空虚な真に注意せよ。
• ${\displaystyle n=1}$ であれば ${\displaystyle \gcd(a_{1})=a_{1}}$ である。
• ${\displaystyle n=2}$ とし、${\displaystyle 0}$ と ${\displaystyle 0}$ の最大公約数は ${\displaystyle 0}$ である^[1][6][7]。ゆえに、一般には最大公約数は最大の公約数ではない^[8]。
• ${\displaystyle n=2}$ とし、${\displaystyle 0}$ でない自然数 ${\displaystyle a_{1}}$ と ${\displaystyle 0}$ の最大公約数は ${\displaystyle a_{1}}$である

自然数が一つ以下の場合は自明なので普通は二つ以上の場合を考えることになるが、二番目の性質により二つの自然数の最大公約数を考えることに帰着する。この定義からアプリオリ^[9]には任意の二つの自然数に最大公約数が存在するかわからないが、実際には単に存在するだけでなく具体的に計算するアルゴリズムがユークリッドの互除法として知られており、この重要な応用がベズーの等式である。

たとえば ${\displaystyle 333}$ と ${\displaystyle 57}$ の最大公約数をユークリッドの互除法により求めてみよう。${\displaystyle 333=57\times 5+48}$ なので ${\displaystyle \gcd(333,57)=\gcd(57,48)}$ である。${\displaystyle 57=48\times 1+9}$ なので ${\displaystyle \gcd(57,48)=\gcd(48,9)}$ である。${\displaystyle 48=9\times 5+3}$ なので ${\displaystyle \gcd(48,9)=\gcd(9,3)}$ である。${\displaystyle 9=3\times 3+0}$ なので ${\displaystyle \gcd(9,3)=\gcd(3,0)=3}$ であり、最大公約数が ${\displaystyle 3}$ であることがわかった。

このように最大公約数の定義や計算に素数や素因数分解などのような高級な概念は全く必要ない^[10]のだが、算術の基本定理が成り立つことを利用して最大公約数を明示的に表すこともできる。つまり、すべての素数から成る集合を ${\displaystyle {\mathfrak {Primes}}}$ として、${\displaystyle a_{1},\dots ,a_{n}}$ を

${\displaystyle a_{i}=\prod _{p\in {\mathfrak {Primes}}}p^{e_{p}(i)}}$

と素因数分解すれば、次が成り立つ^[11]。

${\displaystyle \gcd(a_{1},\dots ,a_{n})=\prod _{p\in {\mathfrak {Primes}}}p^{\min\{e_{p}(1),\ldots ,e_{p}(n)\}}}$

たとえば ${\displaystyle 333=3^{2}\times 37}$ や ${\displaystyle 57=3\times 19}$ と素因数分解できるので、たしかに ${\displaystyle \gcd(333,57)=3}$ となりユークリッドの互除法を用いて得られた値と一致する。

他にも次のような性質が知られている。

• ${\displaystyle \gcd(a,b)\operatorname {lcm} (a,b)=ab}$（ただし ${\displaystyle \operatorname {lcm} }$ は最小公倍数）が成り立つ^{[注釈 2]}。この関係によって最小公倍数を計算するのが一般的である。
• ${\displaystyle \gcd(a,\operatorname {lcm} (b,c))=\operatorname {lcm} (\gcd(a,b),\gcd(a,c))}$ や ${\displaystyle \operatorname {lcm} (a,\gcd(b,c))=\gcd(\operatorname {lcm} (a,b),\operatorname {lcm} (a,c))}$ のような分配則が成り立つ。
• ${\displaystyle \gcd(a,b)=\sum _{k\mid a,b}\varphi (k)}$（ただし ${\displaystyle \varphi (k)}$ はオイラーのトーシェント関数）が成り立つ。
• ${\displaystyle \gcd(a,b)=af(b/a)}$（ただし ${\displaystyle f}$ はトマエ関数）が成り立つ。
• 正の奇数 ${\displaystyle a}$ と自然数 ${\displaystyle b}$ に対して ${\displaystyle \gcd(a,b)=\log _{2}\prod _{k=0}^{a-1}(1+e^{-2\pi ikb/a})}$ が成り立つ^[12]。
• ${\displaystyle \gcd(a,b)=\sum _{k=1}^{a}e^{2\pi ikb/a}\sum _{d\mid a}{\frac {c_{d}(k)}{d}}}$（ただし ${\displaystyle c_{d}(k)}$ はラマヌジャン和（英語版））が成り立つ^[13]。
• ${\displaystyle \gcd(n^{a}-1,n^{b}-1)=n^{\gcd(a,b)}-1}$ が成り立つ^[14]。
• ${\displaystyle \sum _{k=1}^{n}\gcd(k,n)=n\prod _{p\mid n}(1+v_{p}(n)(1-p^{-1}))}$（ただし ${\displaystyle v_{p}(n)}$ は ${\displaystyle n}$ の ${\displaystyle p}$ 進付値）が成り立つ。

特に重要な事実として、組 ${\displaystyle (\mathbb {N} ,\mid )}$ は半順序集合であるのでハッセ図を書くことができ、さらに ${\displaystyle \operatorname {lcm} }$ と ${\displaystyle \gcd }$ をそれぞれ結びと交わりとすれば完備分配束を成し^[1]、${\displaystyle 1}$ が最小元、${\displaystyle 0}$ が最大元になる。したがって圏論的には ${\displaystyle \operatorname {lcm} }$ と ${\displaystyle \gcd }$ はそれぞれ余積と積に対応する。

環論的な定義

初等的な議論では自然数に限定したが、環論的な文脈では上の定義を一般の環（ここでは単位的可換環とする）に置き換えることになる^[15]。よくある定義では条件2の ${\displaystyle b\mid d}$ が ${\displaystyle b\leqq d}$ となっている^{[注釈 3]}ので、通常の大小関係が一般には定義できない環には拡張できないことに注意せよ。一般の環では最大公約数が存在するとは限らない。たとえば ${\displaystyle \mathbb {Z} [x^{2},x^{3}]}$ の元 ${\displaystyle x^{5},x^{6}}$ の最大公約数は存在せず^[16]、${\displaystyle \mathbb {Z} [{\sqrt {-5}}]}$ の元 ${\displaystyle 6,2(1+{\sqrt {-5}})}$ の最大公約数は存在しない。さらに、存在しても一意であるとは限らない。たとえば有理整数環 ${\displaystyle \mathbb {Z} }$ では ${\displaystyle 4}$ と ${\displaystyle 6}$ の最大公約数は ${\displaystyle \pm 2}$ であり、多項式環 ${\displaystyle \mathbb {R} [X]}$ では ${\displaystyle x^{3}-x}$ と ${\displaystyle x^{3}+x^{2}-x-1}$ の最大公約数は ${\displaystyle c(x^{2}-1)}$ (${\displaystyle c\in \mathbb {R} \setminus \{0\}}$) である。しかし考えている環が整域であれば、最大公約数は存在すれば単元倍を除いて一意なのでそれぞれ単に ${\displaystyle 2}$ や ${\displaystyle x^{2}-1}$ と書いてよい。

このように一般の整域でも最大公約数は存在するとは限らないが、すべての二つの元について最大公約数が存在するような整域をGCD整域と言い、特に一意分解整域であればGCD整域である。さらに単項イデアル整域であれば元 ${\displaystyle a_{1},\dots ,a_{n}}$ に対して ${\displaystyle (a_{1},\dots ,a_{n})=(\gcd(a_{1},\dots ,a_{n}))=(a_{1})+\cdots +(a_{n})}$ が成り立ち、より強く多項式環やガウス整数環のようなユークリッド整域であればユークリッドの互除法を用いて最大公約数を求めることができる^[1]。この観点では自然数 ${\displaystyle a,b}$ の最大公約数が有理整数環 ${\displaystyle \mathbb {Z} }$ のイデアル ${\displaystyle (a)+(b)}$ すなわち ${\displaystyle (a,b)}$ の正の生成元であるので、初等的には ${\displaystyle \gcd(a,b)}$ を ${\displaystyle (a,b)}$ と書くことが正当化されていると解釈できる。特に、空集合の生成するイデアルが零イデアルであることから、空集合の最大公約数はやはり ${\displaystyle 0}$ である。