最大公約数

最大公約数（さいだいこうやくすう、）とは、すべての公約数を約数にもつ公約数である。特に正の整数では、最大公約数は通常の大小関係についての最大の公約数と一致し、その存在性はユークリッドの互除法により保証される。
初等的な定義.
以下では、自然数は formula_1 を含むとし、formula_2 が formula_3 を割り切ること（つまり formula_4 となる自然数 formula_5 が存在すること）を formula_6 と表す。
写像 formula_7 を
ように定める。formula_14 を formula_15 の最大公約数といい、formula_16 や formula_17 と表す。formula_18 が成り立つことを formula_15 が互いに素であると言う。
この定義から容易に次のことがわかる。
自然数が一つ以下の場合は自明なので普通は二つ以上の場合を考えることになるが、二番目の性質により二つの自然数の最大公約数を考えることに帰着する。この定義からアプリオリには任意の二つの自然数に最大公約数が存在するかわからないが、実際には単に存在するだけでなく具体的に計算するアルゴリズムがユークリッドの互除法として知られており、この重要な応用がベズーの等式である。
たとえば formula_36 と formula_37 の最大公約数をユークリッドの互除法により求めてみよう。formula_38 なので formula_39 である。formula_40 なので formula_41 である。formula_42 なので formula_43 である。formula_44 なので formula_45 であり、最大公約数が formula_46 であることがわかった。
このように最大公約数の定義や計算に素数や素因数分解などのような高級な概念は全く必要ないのだが、算術の基本定理が成り立つことを利用して最大公約数を明示的に表すこともできる。つまり、すべての素数から成る集合を formula_47 として、formula_15 を
と素因数分解すれば、次が成り立つ。
たとえば formula_51 や formula_52 と素因数分解できるので、たしかに formula_53 となりユークリッドの互除法を用いて得られた値と一致する。
他にも次のような性質が知られている。
特に重要な事実として、組 formula_72 は半順序集合であるのでハッセ図を書くことができ、さらに formula_55 と formula_74 をそれぞれ結びと交わりとすれば完備分配束を成し、formula_75 が最小元、formula_1 が最大元になる。したがって圏論的には formula_55 と formula_74 はそれぞれ余積と積に対応する。
環論的な定義.
初等的な議論では自然数に限定したが、環論的な文脈では上の定義を一般の環（ここでは単位的可換環とする）に置き換えることになる。よくある定義では条件2の formula_13 が formula_80 となっているので、通常の大小関係が一般には定義できない環には拡張できないことに注意せよ。一般の環では最大公約数が存在するとは限らない。たとえば formula_81 の元 formula_82 の最大公約数は存在せず、formula_83 の元 formula_84 の最大公約数は存在しない。さらに、存在しても一意であるとは限らない。たとえば有理整数環 formula_85 では formula_86 と formula_87 の最大公約数は formula_88 であり、多項式環 formula_89 では formula_90 と formula_91 の最大公約数は formula_92 (formula_93) である。しかし考えている環が整域であれば、最大公約数は存在すれば単元倍を除いて一意なのでそれぞれ単に formula_94 や formula_95 と書いてよい。
このように一般の整域でも最大公約数は存在するとは限らないが、すべての二つの元について最大公約数が存在するような整域をGCD整域と言い、特に一意分解整域であればGCD整域である。さらに単項イデアル整域であれば元 formula_15 に対して formula_97 が成り立ち、より強く多項式環やガウス整数環のようなユークリッド整域であればユークリッドの互除法を用いて最大公約数を求めることができる。この観点では自然数 formula_98 の最大公約数が有理整数環 formula_85 のイデアル formula_100 すなわち formula_101 の正の生成元であるので、初等的には formula_102 を formula_101 と書くことが正当化されていると解釈できる。特に、空集合の生成するイデアルが零イデアルであることから、空集合の最大公約数はやはり formula_1 である。