最大公約数
最大公約数（さいだいこうやくすう、テンプレート:Lang-en-short）とは、少なくとも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>を テンプレート:Indentp^{e_p(j)}\ \ \ (e_p(j)\ge 0,\ \ \varepsilon_j=\pm 1) </math>}} と素因数分解したとき、<math>a_1,\ldots, a_n</math>の最大公約数は テンプレート:Indentp^{\min\{e_p(1),\ldots,e_p(n)\}} </math>}} で与えられる。
例えば、<math>30</math>と<math>42</math>の公約数は<math>1,\ 2,\ 3,\ 6</math>であるから、最大公約数は<math>6</math>である。
諸概念
2つ以上の整数<math>a_1,\ldots, a_n</math>の最大公約数が<math>1</math>であるとき、<math>a_1,\ldots, a_n</math>は互いに素であるという。
正整数<math>a,\ b</math>に対して、<math>a</math>と<math>b</math>の最大公約数<math>\mathrm{gcd}(a,\ b)</math>と最小公倍数<math>\mathrm{lcm}(a,\ b)</math>との間には テンプレート:Indent という関係がある。
しかし、この関係式は3つ以上の正整数に対しては一般には成立しない。例えば、<math>a = 2,\ b = 6,\ c = 15</math>とすると、<math>\mathrm{gcd}(a,\ b,\ c) = 1,\ \mathrm{lcm}(a,\ b,\ c) = 30</math>であるが、<math>abc = 180</math>である。
多項式の最大公約数
多項式の公約数のうち、最も次数の高いものを最大公約数という。例えば、<math>x^3-x</math>と<math>x^3+x^2-x-1</math>の最大公約数は<math>x^2-1</math>である。
多項式の最大公約数は定数倍を除いて1つしか存在しない。
一般の環の場合
一般の環上で最大公約数を考えるには、環上の元が素元に分解されることが必要となるが、さらに素元の分解が一意であることが必要である。
例えば、環<math>R = \mathbb{Z}[\sqrt{-5}]</math>とし、<math>R</math>の元<math>6,\ 21</math>の最大公約数を求めてみることにする。<math>6 = 2\cdot 3,\ 21 = 3\cdot 7</math>であり、<math>2,\ 3,\ 7</math>は、<math>R</math>上の素元であるので、最大公約数は<math>3</math>となる。しかし、<math>6 = (1+\sqrt{-5})\cdot(1-\sqrt{-5})</math>、<math>21 = (1+2\sqrt{-5})\cdot(1-2\sqrt{-5})</math>であり、<math>1+\sqrt{-5},\ 1-\sqrt{-5},\ 1+2\sqrt{-5},\ 1-2\sqrt{-5}</math>は<math>R</math>の素元であるので、最大公約数は<math>1</math>となる。
この様に、素元の分解が一意でない場合、最大公約数を一意に定めることができない。
参考文献
関連項目
- ユークリッドの互除法 - 代表的な計算方法
- 公約数
- 公倍数
- 最小公倍数
- 多項式
