最大公約数

最大公約数（さいだいこうやくすう、英: 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つ以上の整数 $a_1,\ldots, a_n$ の最大公約数とは、 $a_1,\ldots, a_n$ の公約数のうち最大の正整数である。

つまり、 $a_1,\ldots, a_n$ を

$a_j = \varepsilon_j\prod_{p;\mathrm{prime}}p^{e_p(j)}\ \ \ (e_p(j)\ge 0,\ \ \varepsilon_j=\pm 1)$

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

$\prod_{p;\mathrm{prime}}p^{\min\{e_p(1),\ldots,e_p(n)\}}$

で与えられる。

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

諸概念[編集]

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

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

$\mathrm{gcd}(a,\ b)\cdot\mathrm{lcm}(a,\ b) = ab$

という関係がある。

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

多項式の最大公約数[編集]

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

多項式の最大公約数は定数倍を除いて1つしか存在しない。

一般の環の場合[編集]

一般の環上で最大公約数を考えるには、環上の元が素元に分解されることが必要となるが、さらに素元の分解が一意であることが必要である。

例えば、環 $R = \mathbb{Z}[\sqrt{-5}]$ とし、 $R$ の元 $6,\ 21$ の最大公約数を求めてみることにする。 $6 = 2\cdot 3,\ 21 = 3\cdot 7$ であり、 $2,\ 3,\ 7$ は、 $R$ 上の素元であるので、最大公約数は $3$ となる。しかし、 $6 = (1+\sqrt{-5})\cdot(1-\sqrt{-5})$ 、 $21 = (1+2\sqrt{-5})\cdot(1-2\sqrt{-5})$ であり、 $1+\sqrt{-5},\ 1-\sqrt{-5},\ 1+2\sqrt{-5},\ 1-2\sqrt{-5}$ は $R$ の素元であるので、最大公約数は $1$ となる。