最大公約数

最大公約数の最新ニュースをまとめて検索！

最大公約数（さいだいこうやくすう、英: greatest common divisor）とは、0 ではない複数の整数の公約数のうち最大のものをさす。たびたび、G.C.D. 、G.C.M.(Greatest Common Measure)もしくは G.C.F.(Greatest Common Factor)等の省略形で記述される。

[編集] 定義

２つ以上の整数 $a_1,\ldots, a_n$ の最大公約数とは、 $a_1,\ldots, a_n$ の公約数のうち最大の正整数である。

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

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

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

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

で与えられる。

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

[編集] 諸概念

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

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

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

という関係がある。

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

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

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

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

[編集] 一般の環の場合

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

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