Mixing
最大公約数
非負整数の整除関係を図示した無限グラフ（ハッセ図）の一部。たとえば8と12の最大公約数は4であり、4と6の最大公約数は2である。
最大公約数（さいだいこうやくすう、英: greatest common divisor）とは、少なくとも一つが0ではない複数の整数の公約数のうち最大の数を指す[1]。具体的にはユークリッドの互除法により求めることができる[2]。
しばしば「G.C.D.」や「G.C.M. (Greatest Common Measure)」、「G.C.F. (Greatest Common Factor)」、「H.C.F. (Highest Common Factor)」等の省略形で記述される。
目次
1 定義
2 諸概念
3 多項式の最大公約数
4 一般の環の場合
5 注
6 参考文献
7 関連項目
定義
少なくとも一つが0でない整数 a1,…,an{displaystyle a_{1},ldots ,a_{n}}
つまり、a1,…,an{displaystyle a_{1},ldots ,a_{n}}
- aj=εj∏pprimepep(j)(ep(j)≥0,εj=±1){displaystyle a_{j}=varepsilon _{j}prod _{p;mathrm {prime} }p^{e_{p}(j)}quad (e_{p}(j)geq 0,;varepsilon _{j}=pm 1)}
と素因数分解したとき、a1,…,an{displaystyle a_{1},ldots ,a_{n}}
- ∏pprimepmin{ep(1),…,ep(n)}{displaystyle prod _{p;mathrm {prime} }p^{min{e_{p}(1),ldots ,e_{p}(n)}}}
で与えられる。
例えば、30 と 42 の公約数は 1, 2, 3, 6 であるから、最大公約数は 6 である。
等価であるが、整数 a1,…,an{displaystyle a_{1},ldots ,a_{n}}
a1x1+⋯+anxn{displaystyle a_{1}x_{1}+dotsb +a_{n}x_{n}}（x1,…,xn{displaystyle x_{1},dotsc ,x_{n}}
は整数）
の形で表すことのできる最小の正整数と定義してもよい。（ベズーの等式参照。）
最大公約数は gcd(a1,…,an){displaystyle gcd(a_{1},dotsc ,a_{n})}
諸概念
2つ以上の整数 a1,…,an{displaystyle a_{1},ldots ,a_{n}}
公約数は最大公約数の約数である。
証明
a,b,c,⋯,z{displaystyle a,b,c,cdots ,z}
このとき、l=g{displaystyle l=g}
①より l>=d{displaystyle l>=d}
g,d{displaystyle g,d}
公倍数は最小公倍数の倍数であるから、a{displaystyle a}
同様に
g,d{displaystyle g,d}
公倍数は最小公倍数の倍数であるから、b{displaystyle b}
これを c{displaystyle c}
すなわち l{displaystyle l}
公約数は最大公約数に等しいかより小さいから l<=g{displaystyle l<=g}
②③より l=g{displaystyle l=g}
正整数 a, b に対して、a と b の最大公約数 gcd (a, b) と最小公倍数 lcm (a, b) との間には
- gcd(a,b)⋅lcm(a,b)=ab{displaystyle operatorname {gcd} (a,b)cdot operatorname {lcm} (a,b)=ab}
という関係がある[3]。
しかし、この関係式は3つ以上の正整数に対しては一般には成立しない。例えば、a = 2, b = 6, c = 15 とすると、gcd (a, b, c) = 1, lcm (a, b, c) = 30 であるが、abc = 180 である。
多項式の最大公約数
多項式の公約数のうち、最も次数の高いものを最大公約数という。例えば、x3−x{displaystyle x^{3}-x}
多項式の最大公約数は、定数倍を除いて一意に決まる。
一般の環の場合
一般にGCD整域（例えば一意分解整域）においても、最大公約数が（単元倍を除いて一意に）存在する。
注
^ Hardy & Wright 2008, p. 24.
^ Hardy & Wright 2008, p. 232, Theorem 207.
^ Hardy & Wright 2008, p. 58, Theorem 52.
参考文献
- 高木貞治 『初等整数論講義』 共立出版、東京、1971年、第2版。
Hardy, G. H.; Wright, E. M. (2008) [1938]. An Introduction to the Theory of Numbers (Sixth ed.). Oxford University Press. ISBN 978-0-19-921985-8. https://books.google.com/books?id=P6uTBqOa3T4C.
関連項目
ユークリッドの互除法 - 代表的な計算方法- 公約数
- 公倍数
- 最小公倍数
- 多項式
| ||||||||
