最大公約数（さいだいこうやくすう、英: 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 , b , c ) {\displaystyle \gcd(\gcd(a,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)} である。