最大公約数（さいだいこうやくすう、）とは、少なくとも1個が0ではない複数の整数の公約数のうち最大のものを指す。しばしば「G.C.D.」や「G.C.M. (Greatest Common Measure)」、「G.C.F. (Greatest Common Factor)」、「H.C.F. (Highest Common Factor)」等の省略形で記述される。2つ以上の整数 formula_1の最大公約数とは、formula_2 の公約数のうち最大の正整数である。つまり、formula_2をと素因数分解したとき、formula_2 の最大公約数はで与えられる。例えば、30 と 42 の公約数は 1, 2, 3, 6 であるから、最大公約数は 6 である。2つ以上の整数 formula_2 の最大公約数が1 であるとき、formula_2 は互いに素であるという。正整数 に対して、 と の最大公約数 と最小公倍数 との間にはという関係がある。しかし、この関係式は3つ以上の正整数に対しては一般には成立しない。例えば、 とすると、, であるが、 である。多項式の公約数のうち、最も次数の高いものを最大公約数という。例えば、formula_10 と formula_11 の最大公約数は formula_12 である。多項式の最大公約数は、定数倍を除いて一意に決まる。一般にGCD整域（例えば一意分解整域）においても、最大公約数が（単元倍を除いて一意に）存在する。

出典:wikipedia