最大公約数のソースを表示

{{Expand English|date=2024年6月}}
[[File:Infinite lattice of divisors.svg|thumb|250px|[[自然数]]の[[整除]]関係を図示した無限グラフ（[[ハッセ図]]）の一部。たとえば8と12の最大公約数は4であり、4と6の最大公約数は2である。]]
'''最大公約数'''（さいだいこうやくすう、{{lang-en-short|greatest common divisor}}{{Efn|文献によっては highest common factor, greatest common factor, greatest common measure などを用いることもある。}}）とは、すべての[[公約数]]を[[約数]]にもつ公約数である。特に正の[[整数]]では、最大公約数は通常の大小関係についての最大の公約数と一致し、その存在性は[[ユークリッドの互除法]]により保証される。

== 初等的な定義 ==
以下では、[[自然数]]は <math>0</math> を含むとし、<math>a</math> が <math>b</math> を[[割り切れる|割り切る]]こと（つまり <math>b=ca</math> となる自然数 <math>c</math> が存在すること）を <math>a\mid b</math> と表す。

[[写像]] <math>\gcd\colon\N^n\to\N;(a_1,\dots,a_n)\mapsto d</math> を

# すべての <math>1\leqq i\leqq n</math> に対して <math>d\mid a_i</math> であり、
# すべての自然数 <math>b</math> に対し、すべての <math>1\leqq i\leqq n</math> に対して <math>b\mid a_i</math> ならば <math>b\mid d</math> となる

ように定める<ref name=":0">{{Cite web|url=https://ncatlab.org/nlab/show/greatest+common+divisor|title=greatest common divisor|accessdate=2021-12-17|publisher=nLab}}</ref><ref name=":1">{{Cite web|title=elementary number theory - GCD of an empty set?|url=https://math.stackexchange.com/questions/1755266/gcd-of-an-empty-set|website=Mathematics Stack Exchange|accessdate=2021-12-17}}</ref><ref>{{Cite web|title=gcd domain|url=https://planetmath.org/gcddomain|website=planetmath.org|accessdate=2021-12-17}}</ref><ref>加藤・中井（2016）定義 2.4.3</ref>。<math>d</math> を <math>a_1,\dots,a_n</math> の最大公約数といい、<math>\gcd(a_1,\dots,a_n)</math> や <math>(a_1,\dots,a_n)</math> と表す。<math>\gcd(a_1,\dots,a_n)=1</math> が成り立つことを <math>a_1,\dots,a_n</math> が[[互いに素 (整数論)|互いに素]]であると言う。

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

* <math>\gcd(a,b)=\gcd(b,a)</math> が成り立つ。
*<math>\gcd(\gcd(a,b),c)=\gcd(a,\gcd(b,c))=\gcd(a,b,c)</math> が成り立つ<ref name=":1" />。
*最大公約数は存在すれば一意である<ref>加藤・中井（2016）命題 2.4.4</ref>。
* <math>n=0</math> であれば（つまり空集合の）最大公約数は <math>0</math> である<ref name=":1" />。[[空積]]が <math>1=\{\varnothing\}</math> であることと[[空虚な真]]に注意せよ。
* <math>n=1</math> であれば <math>\gcd(a_1)=a_1</math> である。
* <math>n=2</math> とし、<math>0</math> と <math>0</math> の最大公約数は <math>0</math> である<ref name=":0">{{Cite web|url=https://ncatlab.org/nlab/show/greatest+common+divisor|title=greatest common divisor|accessdate=2021-12-17|publisher=nLab}}</ref><ref>{{Cite web|title=elementary number theory - What is $\gcd(0,0)$?|url=https://math.stackexchange.com/questions/495119/what-is-gcd0-0|website=Mathematics Stack Exchange|accessdate=2021-12-17}}</ref><ref>{{Cite web|title=gcd(0,0) - Wolfram{{!}}Alpha|url=https://ja.wolframalpha.com/|website=ja.wolframalpha.com|accessdate=2021-12-17}}</ref>。ゆえに、一般には'''最大公約数は最大の公約数ではない<ref>加藤・中井（2016）p. 42</ref>'''。
* <math>n=2</math> とし、<math>0</math> でない自然数 <math>a_1</math> と <math>0</math> の最大公約数は <math>a_1</math>である

自然数が一つ以下の場合は自明なので普通は二つ以上の場合を考えることになるが、二番目の性質により二つの自然数の最大公約数を考えることに帰着する。この定義からアプリオリ<ref>{{Cite web|title=philosophy of mathematics - What does a priori mean in a math paper?|url=https://philosophy.stackexchange.com/questions/72702/what-does-a-priori-mean-in-a-math-paper|website=Philosophy Stack Exchange|accessdate=2021-12-17}}</ref>には任意の二つの自然数に最大公約数が存在するかわからないが、実際には単に存在するだけでなく具体的に計算するアルゴリズムが[[ユークリッドの互除法]]として知られており、この重要な応用が[[ベズーの等式]]である。

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

このように'''最大公約数の定義や計算に[[素数]]や[[素因数分解]]などのような高級な概念は全く必要ない'''<ref>加藤・中井（2016）p. 49</ref>のだが、[[算術の基本定理]]が成り立つことを利用して最大公約数を明示的に表すこともできる。つまり、すべての素数から成る集合を <math>\mathfrak{Primes}</math> として、<math>a_1,\dots,a_n</math> を
:<math>a_i=\prod_{p\in\mathfrak{Primes}} p^{e_p (i)}</math>
と素因数分解すれば、次が成り立つ<ref>加藤・中井（2016）命題 2.9.4</ref>。
:<math>\gcd(a_1,\dots,a_n)=\prod_{p\in\mathfrak{Primes}} p^{\min\{e_p(1),\ldots ,e_p(n)\}}</math>
たとえば <math>333=3^2\times 37</math> や <math>57=3\times 19</math> と素因数分解できるので、たしかに <math>\gcd(333,57)=3</math> となりユークリッドの互除法を用いて得られた値と一致する。

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

* <math>\gcd(a,b)\operatorname{lcm}(a,b)=ab</math>（ただし <math>\operatorname{lcm}</math> は[[最小公倍数]]）が成り立つ{{Efn|この性質は引数が二つ以下の場合でしか一般に成り立たない。たとえば2と6と15であれば、左辺は30で右辺は180となり等号は成り立たない。この事態は素因数分解による表式を考えることにより理解される。}}。この関係によって最小公倍数を計算するのが一般的である。
* <math>\gcd(a,\operatorname{lcm}(b,c))=\operatorname{lcm}(\gcd(a,b),\gcd(a,c))</math> や <math>\operatorname{lcm}(a,\gcd(b,c))=\gcd(\operatorname{lcm}(a,b),\operatorname{lcm}(a,c))</math> のような[[分配法則|分配則]]が成り立つ。
* <math>\gcd(a,b)=\sum_{k\mid a,b}\varphi(k)</math>（ただし <math>\varphi(k)</math> は[[オイラーのトーシェント関数]]）が成り立つ。
* <math>\gcd(a,b)=af(b/a)</math>（ただし <math>f</math> は[[トマエ関数]]）が成り立つ。
* 正の奇数 <math>a</math> と自然数 <math>b</math> に対して <math>\gcd(a,b)=\log_2\prod_{k=0}^{a-1}(1+e^{-2\pi ikb/a})</math> が成り立つ<ref>{{Cite journal|author=Slavin, K. R.|year=2008|title=Q-Binomials and the Greatest Common Divisor|url=http://math.colgate.edu/~integers/i5/i5.pdf|journal=INTEGERS: The Electronic Journal of Combinatorial Number Theory|volume=8|page=A5|format=PDF}}</ref>。
* <math>\gcd(a,b)=\sum_{k=1}^a e^{2\pi ikb/a}\sum_{d\mid a}\frac{c_d(k)}{d}</math>（ただし <math>c_d(k)</math> は{{仮リンク|ラマヌジャン和|en|Ramanujan's sum}}）が成り立つ<ref>{{Cite journal|author=Schramm, W.|year=2008|title=The Fourier transform of functions of the greatest common divisor|url=http://math.colgate.edu/~integers/i50/i50.pdf|journal=INTEGERS: The Electronic Journal of Combinatorial Number Theory|volume=8|page=A50|format=PDF}}</ref>。
* <math>\gcd(n^a-1,n^b-1)=n^{\gcd(a,b)}-1</math> が成り立つ<ref>{{Cite web|title=elementary number theory - Prove that $\gcd(a^n - 1, a^m - 1) = a^{\gcd(n, m)} - 1$|url=https://math.stackexchange.com/questions/7473/prove-that-gcdan-1-am-1-a-gcdn-m-1|website=Mathematics Stack Exchange|accessdate=2021-12-17}}</ref>。
* <math>\sum_{k=1}^n\gcd(k,n)=n\prod_{p\mid n}(1+v_p(n)(1-p^{-1}))</math>（ただし <math>v_p(n)</math> は <math>n</math> の [[P進付値|<math>p</math> 進付値]]）が成り立つ。

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

== 環論的な定義 ==
初等的な議論では自然数に限定したが、[[環 (数学)|環]]論的な文脈では上の定義を一般の環（ここでは単位的可換環とする）に置き換えることになる<ref>{{Cite web|title=gcd domain|url=https://planetmath.org/gcddomain|website=planetmath.org|accessdate=2021-12-17}}</ref>。よくある定義では条件2の <math>b\mid d</math> が <math>b\leqq d</math> となっている{{Efn|たとえば高木貞治（1971）『初等整数論講義』や日本数学会（2012）『岩波数学辞典 第4版』はこの流儀を採用している。}}ので、通常の大小関係が一般には定義できない環には拡張できないことに注意せよ。'''一般の環では最大公約数が存在するとは限らない'''。たとえば <math>\Z[x^2,x^3]</math> の元 <math>x^5, x^6</math> の最大公約数は存在せず<ref>{{Cite web|title=greatest common divisor|url=https://planetmath.org/greatestcommondivisor|website=planetmath.org|accessdate=2021-12-17}}</ref>、<math>\Z[\sqrt{-5}]</math> の元 <math>6, 2(1+\sqrt{-5})</math> の最大公約数は存在しない。さらに、'''存在しても一意であるとは限らない'''。たとえば[[有理整数環]] <math>\Z</math> では <math>4</math> と <math>6</math> の最大公約数は <math>\pm2</math> であり、[[多項式環]] <math>\R[X]</math> では <math>x^3-x</math> と <math>x^3+x^2-x-1</math> の最大公約数は <math>c(x^2-1)</math> (<math>c\in\R\setminus\{0\}</math>) である。しかし考えている環が[[整域]]であれば、最大公約数は存在すれば'''単元倍を除いて一意'''なのでそれぞれ単に <math>2</math> や <math>x^2-1</math> と書いてよい。

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

== 脚注 ==

=== 注釈 ===
{{Notelist}}

=== 出典 ===
{{Reflist}}

== 参考文献 ==
*加藤文元・中井保行（2016）『天に向かって続く数』日本評論社．
*[[nlab:greatest+common+divisor|nLab - “greatest common divisor”]] (英語)

== 関連項目 ==
{{ウィキプロジェクトリンク|数学|[[画像:Nuvola apps edu mathematics blue-p.svg|34px|Project:数学]]}}
*[[ユークリッドの互除法]]
*[[公約数]]
*[[公倍数]]
*[[最小公倍数]]
*[[GCD整域]]
*[[ユークリッド整域]]
*[[RADWIMPS 3〜無人島に持っていき忘れた一枚〜|最大公約数]] - [[RADWIMPS]]の楽曲。

{{二項演算}}

{{DEFAULTSORT:さいたいこうやくすう}}
[[Category:数論]]
[[Category:初等数学]]
[[Category:数学に関する記事]]
[[Category:環論]]