最大公約数

この記事は英語版の対応するページを翻訳することにより充実させることができます。（2024年6月） 翻訳前に重要な指示を読むには右にある[表示]をクリックしてください。 英語版記事を日本語へ機械翻訳したバージョン（Google翻訳）。 万が一翻訳の手がかりとして機械翻訳を用いた場合、翻訳者は必ず翻訳元原文を参照して機械翻訳の誤りを訂正し、正確な翻訳にしなければなりません。これが成されていない場合、記事は削除の方針G-3に基づき、削除される可能性があります。 信頼性が低いまたは低品質な文章を翻訳しないでください。もし可能ならば、文章を他言語版記事に示された文献で正しいかどうかを確認してください。 履歴継承を行うため、要約欄に翻訳元となった記事のページ名・版について記述する必要があります。記述方法については、Wikipedia:翻訳のガイドライン#要約欄への記入を参照ください。 翻訳後、{{翻訳告知|en|Greatest common divisor|…}}をノートに追加することもできます。 Wikipedia:翻訳のガイドラインに、より詳細な翻訳の手順・指針についての説明があります。

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

以下では、自然数は ${\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}$ である。

• 加藤文元・中井保行（2016）『天に向かって続く数』日本評論社．
• nLab - “greatest common divisor” (英語)

プロジェクト 数学

• ユークリッドの互除法
• 公約数
• 公倍数
• 最小公倍数
• GCD整域
• ユークリッド整域
• 最大公約数 - RADWIMPSの楽曲。

表 話 編 歴 二項演算
四則演算	加法 減法 乗法 除法
ハイパー演算	加法 乗法 冪乗 テトレーション ペンテーション
その他	対数 二項係数 スターリング数 階乗冪 剰余演算 最小公倍数 最大公約数 平方剰余記号
カテゴリ