最大公約数

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

最大公約数(さいだいこうやくすう、: 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)\}}

で与えられる。

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

諸概念[編集]

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

正整数a,\ bに対して、abの最大公約数\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-xx^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となる。

この様に、素元の分解が一意でない場合、最大公約数を一意に定めることができない。

参考文献[編集]

  • 高木貞治 『初等整数論講義第2版』 共立出版、東京、1971年

関連項目[編集]