最大公約数
最大公約数(さいだいこうやくすう、greatest common divisor文献によっては highest common factor, greatest common factor, greatest common measure などを用いることもある。)とは、すべての公約数を約数にもつ公約数である。特に正の整数では、最大公約数は通常の大小関係についての最大の公約数と一致し、その存在性はユークリッドの互除法により保証される。
以下では、自然数は 0 を含むとし、a が b を割り切ること(つまり b=ca となる自然数 c が存在すること)を a\mid b と表す。
写像 \gcd\colon\N^n\to\N;(a_1,\dots,a_n)\mapsto d を
すべての 1\leqq i\leqq n に対して d\mid a_i であり、
すべての自然数 b に対し、すべての 1\leqq i\leqq n に対して b\mid a_i ならば b\mid d となる
ように定める。d を a_1,\dots,a_n の最大公約数といい、\gcd(a_1,\dots,a_n) や (a_1,\dots,a_n) と表す。\gcd(a_1,\dots,a_n)=1 が成り立つことを a_1,\dots,a_n が互いに素であると言う。
この定義から容易に次のことがわかる。
\gcd(a,b)=\gcd(b,a) が成り立つ。
\gcd(\gcd(a,b),c)=\gcd(a,b,c) が成り立つ。
最大公約数は存在すれば一意である。
n=0 であれば(つまり空集合の)最大公約数は 0 である。空積が 1=\{\varnothing\} であることと空なる真に注意せよ。
n=1 であれば \gcd(a_1)=a_1 である。
n=2 とし、0 と 0 の最大公約数は 0 である。ゆえに、一般には最大公約数は最大の公約数ではない。
n=2 とし、0 でない自然数 a_1 と 0 の最大公約数は a_1である
自然数が一つ以下の場合は自明なので普通は二つ以上の場合を考えることになるが、二番目の性質により二つの自然数の最大公約数を考えることに帰着する。この定義からアプリオリには任意の二つの自然数に最大公約数が存在するかわからないが、実際には単に存在するだけでなく具体的に計算するアルゴリズムがユークリッドの互除法として知られており、この重要な応用がベズーの等式である。
たとえば 333 と 57 の最大公約数をユークリッドの互除法により求めてみよう。333=57\times 5+48 なので \gcd(333,57)=\gcd(57,48) である。57=48\times 1+9 なので \gcd(57,48)=\gcd(48,9) である。48=9\times 5+3 なので \gcd(48,9)=\gcd(9,3) である。9=3\times 3+0 なので \gcd(9,3)=\gcd(3,0)=3 であり、最大公約数が 3 であることがわかった。
このように最大公約数の定義や計算に素数や素因数分解などのような高級な概念は全く必要ないのだが、算術の基本定理が成り立つことを利用して最大公約数を明示的に表すこともできる。つまり、すべての素数から成る集合を \mathfrak{Primes} として、a_1,\dots,a_n を
a_i=\prod_{p\in\mathfrak{Primes} p^{e_p (i)}
と素因数分解すれば、次が成り立つ。
\gcd(a_1,\dots,a_n)=\prod_{p\in\mathfrak{Primes} p^{\min\{e_p(1),\ldots ,e_p(n)\}
たとえば 333=3^2\times 37 や 57=3\times 19 と素因数分解できるので、たしかに \gcd(333,57)=3 となりユークリッドの互除法を用いて得られた値と一致する。
他にも次のような性質が知られている。
\gcd(a,b)\operatorname{lcm}(a,b)=ab(ただし \operatorname{lcm} は最小公倍数)が成り立つこの性質は引数が二つ以下の場合でしか一般に成り立たない。たとえば2と6と15であれば、左辺は30で右辺は180となり等号は成り立たない。この事態は素因数分解による表式を考えることにより理解される。。この関係によって最小公倍数を計算するのが一般的である。
\gcd(a,\operatorname{lcm}(b,c))=\operatorname{lcm}(\gcd(a,b),\gcd(a,c)) や \operatorname{lcm}(a,\gcd(b,c))=\gcd(\operatorname{lcm}(a,b),\operatorname{lcm}(a,c)) のような分配則が成り立つ。
\gcd(a,b)=\sum_{k\mid a,b}\varphi(k)(ただし \varphi(k) はオイラーのトーシェント関数)が成り立つ。
\gcd(a,b)=af(b/a)(ただし f はトマエ関数)が成り立つ。
正の奇数 a と自然数 b に対して \gcd(a,b)=\log_2\prod_{k=0}^{a-1}(1+e^{-2\pi ikb/a}) が成り立つ。
\gcd(a,b)=\sum_{k=1}^a e^{2\pi ikb/a}\sum_{d\mid a}\frac{c_d(k)}{d}(ただし c_d(k) はラマヌジャン和)が成り立つ。
\gcd(n^a-1,n^b-1)=n^{\gcd(a,b)}-1 が成り立つ。
\sum_{k=1}^n\gcd(k,n)=n\prod_{p\mid n}(1+v_p(n)(1-p^{-1}))(ただし v_p(n) は n の p 進付値)が成り立つ。
特に重要な事実として、組 (\N,\mid) は半順序集合であるのでハッセ図を書くことができ、さらに \operatorname{lcm} と \gcd をそれぞれ結びと交わりとすれば完備分配束を成し、1 が最小元、0 が最大元になる。したがって圏論的には \operatorname{lcm} と \gcd はそれぞれ余積と積に対応する。
初等的な議論では自然数に限定したが、環論的な文脈では上の定義を一般の環(ここでは単位的可換環とする)に置き換えることになる。よくある定義では条件2の b\mid d が b\leqq d となっているたとえば高木貞治(1971)『初等整数論講義』や日本数学会(2012)『岩波数学辞典 第4版』はこの流儀を採用している。ので、通常の大小関係が一般には定義できない環には拡張できないことに注意せよ。一般の環では最大公約数が存在するとは限らない。たとえば \Z[x^2,x^3] の元 x^5, x^6 の最大公約数は存在せず、\Z[\sqrt{-5}] の元 6, 2(1+\sqrt{-5}) の最大公約数は存在しない。さらに、存在しても一意であるとは限らない。たとえば有理整数環 \Z では 4 と 6 の最大公約数は \pm2 であり、多項式環 \R[X] では x^3-x と x^3+x^2-x-1 の最大公約数は c(x^2-1) (c\in\R\setminus\{0\}) である。しかし考えている環が整域であれば、最大公約数は存在すれば単元倍を除いて一意なのでそれぞれ単に 2 や x^2-1 と書いてよい。
このように一般の整域でも最大公約数は存在するとは限らないが、すべての二つの元について最大公約数が存在するような整域をGCD整域と言い、特に一意分解整域であればGCD整域である。さらに単項イデアル整域であれば元 a_1,\dots,a_n に対して (a_1,\dots,a_n)=(\gcd(a_1,\dots,a_n))=(a_1)+\cdots+(a_n) が成り立ち、より強く多項式環やガウス整数環のようなユークリッド整域であればユークリッドの互除法を用いて最大公約数を求めることができる。この観点では自然数 a, b の最大公約数が有理整数環 \Z のイデアル (a)+(b) すなわち (a,b) の正の生成元であるので、初等的には \gcd(a,b) を (a,b) と書くことが正当化されていると解釈できる。特に、空集合の生成するイデアルが零イデアルであることから、空集合の最大公約数はやはり 0 である。