最大公約数

非負整数の整除関係を図示した無限グラフ（ハッセ図）の一部。たとえば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)」等の省略形で記述される事もある。

定義[編集]

少なくとも一つが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)\}}

で与えられる。

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

等価であるが、整数 $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$ 。これで証明を完了する。