非負整数の
整除関係を図示した無限グラフ(
ハッセ図)の一部。たとえば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でない整数
の最大公約数とは、
の公約数のうち最大の数である。(定義から正整数となる。)
つまり、
を

と素因数分解したとき、
の最大公約数は

で与えられる。
例えば、30 と 42 の公約数は 1, 2, 3, 6 であるから、最大公約数は 6 である。
等価であるが、整数
の最大公約数を
(
は整数)
の形で表すことのできる最小の正整数と定義してもよい。(ベズーの等式参照。)
最大公約数は
あるいは
などの記号で表される。
諸概念[編集]
2つ以上の整数
の最大公約数が1 であるとき、
は互いに素であるという。
公約数は最大公約数の約数である。
証明
の最大公倍数を
、任意の公約数を
とする.
と
の最小公倍数を
とする…①
このとき、
であることを示して証明を完了することとする.
①より
、
。…②
はともに
の約数より
は
と
の公倍数。
公倍数は最小公倍数の倍数であるから、
は
の倍数、すなわち
は
の約数。
同様に
はともに
の約数より
は
と
の公倍数。
公倍数は最小公倍数の倍数であるから、
は
の倍数、すなわち
は
の約数。
これを
から
まで繰り返し、
は
のそれぞれに対して約数であることがわかる。
すなわち
は
の公約数。
公約数は最大公約数に等しいかより小さいから
。…③
②③より
。これで証明を完了する。
正整数 a, b に対して、a と b の最大公約数 gcd (a, b) と最小公倍数 lcm (a, b) との間には

という関係がある。
しかし、この関係式は3つ以上の正整数に対しては一般には成立しない。例えば、a = 2, b = 6, c = 15 とすると、gcd (a, b, c) = 1, lcm (a, b, c) = 30 であるが、abc = 180 である。
多項式の最大公約数[編集]
多項式の公約数のうち、最も次数の高いものを最大公約数という。例えば、
と
の最大公約数は
である。
多項式の最大公約数は、定数倍を除いて一意に決まる。
一般の環の場合[編集]
一般にGCD整域(例えば一意分解整域)においても、最大公約数が(単元倍を除いて一意に)存在する。
参考文献[編集]
関連項目[編集]