最大公約数

非負整数の整除関係を図示した無限グラフ（ハッセ図）の一部。たとえば8と12の最大公約数は4であり、4と6の最大公約数は2である。

最大公約数（さいだいこうやくすう、英: greatest common divisor）とは、少なくとも一つが0ではない複数の整数の公約数のうち最大の数を指す。具体的にはユークリッドの互除法により求めることができる。

「G.C.D.」や「G.C.M. (Greatest Common Measure)」、「G.C.F. (Greatest Common Factor)」、「H.C.F. (Highest Common Factor)」等の省略形で記述される事もある。

定義

少なくとも一つが0でない整数 $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)}\quad (e_{p}(j)\geq 0,\;\varepsilon _{j}=\pm 1)$

と素因数分解したとき、$a_{1},\ldots ,a_{n}$ の最大公約数は

$\prod _{p\;\mathrm {prime} }p^{\min\{e_{p}(1),\ldots ,e_{p}(n)\}}$

で与えられる。

例えば、12 と 16 の公約数は 1, 2, 4 であるから、最大公約数は 4 である。

等価であるが、整数 $a_{1},\ldots ,a_{n}$ の最大公約数を

$a_{1}x_{1}+\dotsb +a_{n}x_{n}$ （$x_{1},\dotsc ,x_{n}$ は整数）

の形で表すことのできる最小の正整数と定義してもよい。（ベズーの等式参照。）

最大公約数は $\gcd(a_{1},\dotsc ,a_{n})$ あるいは $(a_{1},\dotsc ,a_{n})$ などの記号で表される。

諸概念

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

公約数は最大公約数の約数である。

証明

$a,b,c,\cdots ,z$ の最大公約数を $g$、任意の公約数を $d$ とする．$g$ と $d$ の最小公倍数を $l$ とする…① このとき、$l=g$ であることを示して証明を完了することとする。 ①より $l>=d$、$l>=g$。…② $g,d$ はともに $a$ の約数より $a$ は $g$ と $d$ の公倍数。 公倍数は最小公倍数の倍数であるから、$a$ は $l$ の倍数、すなわち $l$ は $a$ の約数。 同様に $g,d$ はともに $b$ の約数より $b$ は $g$ と $d$ の公倍数。 公倍数は最小公倍数の倍数であるから、$b$ は $l$ の倍数、すなわち $l$ は $b$ の約数。 これを $c$ から $z$ まで繰り返し、$l$ は $c\cdots z$ のそれぞれに対して約数であることがわかる。 すなわち $l$ は $a,b,c,\cdots ,z$ の公約数。 公約数は最大公約数に等しいかより小さいから $l<=g$。…③ ②③より $l=g$。これで証明を完了する。

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

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

という関係がある。

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

多項式の最大公約数

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

多項式の最大公約数は、定数倍を除いて一意に決まる。

一般の環の場合

一般にGCD整域（例えば一意分解整域）においても、最大公約数が（単元倍を除いて一意に）存在する。

参考文献

• 高木貞治『初等整数論講義』共立出版、東京、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 

関連項目

• ユークリッドの互除法 - 代表的な計算方法
• 公約数
• 公倍数
• 最小公倍数
• 多項式