最大公約数

40と15に関する次の要素が埋め込まれた図: 積(600)、商と剰余(40÷15=2余り10)、最小公倍数(120)、最大公約数(5)、比(8:3)

幾何学的に２つの整数(WとH)及びその最大公約数並びに最小公倍数を長さとして表せる。この図では、WとHを長方形の幅と高さに割り当て、最大公約数をユークリッドの互除法に基づく方法で長さとして求めだし、長方形の面積(WとHの積)を最大公約数で割った結果として最小公倍数も長さとして求めだしている。

最大公約数（さいだいこうやくすう、英: greatest common divisor）とは、少なくとも1個が0ではない複数の整数の公約数のうち最大のものを指す。

しばしば「G.C.D.」や「G.C.M. (Greatest Common Measure)」、「G.C.F. (Greatest Common Factor)」、「H.C.F. (Highest Common Factor)」等の省略形で記述される。

定義

2つ以上の整数 [math]a_1,\ldots ,a_n[/math]の最大公約数とは、[math]a_1,\ldots, a_n[/math] の公約数のうち最大の正整数である。

つまり、[math]a_1,\ldots, a_n[/math]を

[math]a_j =\varepsilon_j\prod_{p\;\mathrm{prime}} p^{e_p (j)} \quad (e_p (j)\ge 0,\;\varepsilon_j =\pm 1)[/math]

と素因数分解したとき、[math]a_1,\ldots, a_n[/math] の最大公約数は

[math]\prod_{p\;\mathrm{prime}} p^{\min\{e_p(1),\ldots ,e_p(n)\}}[/math]

で与えられる。

例えば、30 と 42 の公約数は 1, 2, 3, 6 であるから、最大公約数は 6 である。

2つ以上の整数 [math]a_1,\ldots, a_n[/math] の最大公約数が1 であるとき、[math]a_1,\ldots, a_n[/math] は互いに素であるという。

正整数 $a, b$ に対して、 $a$ と $b$ の最大公約数 $gcd (a, b)$ と最小公倍数 $lcm (a, b)$ との間には

[math]\operatorname{gcd} (a,b)\cdot \operatorname{lcm} (a,b)=ab[/math]

という関係がある。

しかし、この関係式は3つ以上の正整数に対しては一般には成立しない。例えば、 $a = 2, b = 6, c = 15$ とすると、 $gcd (a, b, c) = 1$ , $lcm (a, b, c) = 30$ であるが、 $abc = 180$ である。

多項式の公約数のうち、最も次数の高いものを最大公約数という。例えば、[math]x^3 -x[/math] と [math]x^3 +x^2 -x-1[/math] の最大公約数は [math]x^2 -1[/math] である。

多項式の最大公約数は、定数倍を除いて一意に決まる。

一般にGCD整域（例えば一意分解整域）においても、最大公約数が（単元倍を除いて一意に）存在する。