最大公約数（さいだいこうやくすう、英: greatest common divisor[注釈 1]）とは、すべての公約数を約数にもつ公約数である。特に正の整数では、最大公約数は通常の大小関係についての最大の公約数と一致し、その存在性はユークリッドの互除法により保証される。
初等的な定義

以下では、自然数は 0 {\displaystyle 0} を含むとし、 a {\displaystyle a} が b {\displaystyle b} を割り切ること（つまり b = c a {\displaystyle b=ca} となる自然数 c {\displaystyle c} が存在すること）を a ∣ b {\displaystyle a\mid b} と表す。

写像 gcd : N n → N ; ( a 1 , … , a n ) ↦ d {\displaystyle \gcd \colon \mathbb {N} ^{n}\to \mathbb {N} ;(a_{1},\dots ,a_{n})\mapsto d} を
すべての 1 ≦ i ≦ n {\displaystyle 1\leqq i\leqq n} に対して d ∣ a i {\displaystyle d\mid a_{i}} であり、

すべての自然数 b {\displaystyle b} に対し、すべての 1 ≦ i ≦ n {\displaystyle 1\leqq i\leqq n} に対して b ∣ a i {\displaystyle b\mid a_{i}} ならば b ∣ d {\displaystyle b\mid d} となる

ように定める[1][2][3][4]。 d {\displaystyle d} を a 1 , … , a n {\displaystyle a_{1},\dots ,a_{n}} の最大公約数といい、 gcd ( a 1 , … , a n ) {\displaystyle \gcd(a_{1},\dots ,a_{n})} や ( a 1 , … , a n ) {\displaystyle (a_{1},\dots ,a_{n})} と表す。 gcd ( a 1 , … , a n ) = 1 {\displaystyle \gcd(a_{1},\dots ,a_{n})=1} が成り立つことを a 1 , … , a n {\displaystyle a_{1},\dots ,a_{n}} が互いに素であると言う。

この定義から容易に次のことがわかる。

gcd ( a , b ) = gcd ( b , a ) {\displaystyle \gcd(a,b)=\gcd(b,a)} が成り立つ。

gcd ( gcd ( a , b ) , c ) = gcd ( a , gcd ( b , c ) ) = gcd ( a , b , c ) {\displaystyle \gcd(\gcd(a,b),c)=\gcd(a,\gcd(b,c))=\gcd(a,b,c)} が成り立つ[2]。

最大公約数は存在すれば一意である[5]。

n = 0 {\displaystyle n=0} であれば（つまり空集合の）最大公約数は 0 {\displaystyle 0} である[2]。空積が 1 = { ∅ } {\displaystyle 1=\{\varnothing \}} であることと空虚な真に注意せよ。

n = 1 {\displaystyle n=1} であれば gcd ( a 1 ) = a 1 {\displaystyle \gcd(a_{1})=a_{1}} である。

n = 2 {\displaystyle n=2} とし、 0 {\displaystyle 0} と 0 {\displaystyle 0} の最大公約数は 0 {\displaystyle 0} である[1][6][7]。ゆえに、一般には最大公約数は最大の公約数ではない[8]。

n = 2 {\displaystyle n=2} とし、 0 {\displaystyle 0} でない自然数 a 1 {\displaystyle a_{1}} と 0 {\displaystyle 0} の最大公約数は a 1 {\displaystyle a_{1}} である

自然数が一つ以下の場合は自明なので普通は二つ以上の場合を考えることになるが、二番目の性質により二つの自然数の最大公約数を考えることに帰着する。この定義からアプリオリ[9]には任意の二つの自然数に最大公約数が存在するかわからないが、実際には単に存在するだけでなく具体的に計算するアルゴリズムがユークリッドの互除法として知られており、この重要な応用がベズーの等式である。

たとえば 333 {\displaystyle 333} と 57 {\displaystyle 57} の最大公約数をユークリッドの互除法により求めてみよう。 333 = 57 × 5 + 48 {\displaystyle 333=57\times 5+48} なので gcd ( 333 , 57 ) = gcd ( 57 , 48 ) {\displaystyle \gcd(333,57)=\gcd(57,48)} である。 57 = 48 × 1 + 9 {\displaystyle 57=48\times 1+9} なので gcd ( 57 , 48 ) = gcd ( 48 , 9 ) {\displaystyle \gcd(57,48)=\gcd(48,9)} である。 48 = 9 × 5 + 3 {\displaystyle 48=9\times 5+3} なので gcd ( 48 , 9 ) = gcd ( 9 , 3 ) {\displaystyle \gcd(48,9)=\gcd(9,3)} である。 9 = 3 × 3 + 0 {\displaystyle 9=3\times 3+0} なので gcd ( 9 , 3 ) = gcd ( 3 , 0 ) = 3 {\displaystyle \gcd(9,3)=\gcd(3,0)=3} であり、最大公約数が 3 {\displaystyle 3} であることがわかった。

このように最大公約数の定義や計算に素数や素因数分解などのような高級な概念は全く必要ない[10]のだが、算術の基本定理が成り立つことを利用して最大公約数を明示的に表すこともできる。つまり、すべての素数から成る集合を P r i m e s {\displaystyle {\mathfrak {Primes}}} として、 a 1 , … , a n {\displaystyle a_{1},\dots ,a_{n}} を a i = ∏ p ∈ P r i m e s p e p ( i ) {\displaystyle a_{i}=\prod _{p\in {\mathfrak {Primes}}}p^{e_{p}(i)}}

と素因数分解すれば、次が成り立つ[11]。 gcd ( a 1 , … , a n ) = ∏ p ∈ P r i m e s p min { e p ( 1 ) , … , e p ( n ) } {\displaystyle \gcd(a_{1},\dots ,a_{n})=\prod _{p\in {\mathfrak {Primes}}}p^{\min\{e_{p}(1),\ldots ,e_{p}(n)\}}}

たとえば 333 = 3 2 × 37 {\displaystyle 333=3^{2}\times 37} や 57 = 3 × 19 {\displaystyle 57=3\times 19} と素因数分解できるので、たしかに gcd ( 333 , 57 ) = 3 {\displaystyle \gcd(333,57)=3} となりユークリッドの互除法を用いて得られた値と一致する。

他にも次のような性質が知られている。

gcd ( a , b ) lcm ⁡ ( a , b ) = a b {\displaystyle \gcd(a,b)\operatorname {lcm} (a,b)=ab} （ただし lcm {\displaystyle \operatorname {lcm} } は最小公倍数）が成り立つ[注釈 2]。この関係によって最小公倍数を計算するのが一般的である。

gcd ( a , lcm ⁡ ( b , c ) ) = lcm ⁡ ( gcd ( a , b ) , gcd ( a , c ) ) {\displaystyle \gcd(a,\operatorname {lcm} (b,c))=\operatorname {lcm} (\gcd(a,b),\gcd(a,c))} や lcm ⁡ ( a , gcd ( b , c ) ) = gcd ( lcm ⁡ ( a , b ) , lcm ⁡ ( a , c ) ) {\displaystyle \operatorname {lcm} (a,\gcd(b,c))=\gcd(\operatorname {lcm} (a,b),\operatorname {lcm} (a,c))} のような分配則が成り立つ。