以下では、自然数は
を含むとし、
が
を割り切ること(つまり
となる自然数
が存在すること)を
と表す。
写像 ;(a_{1},\dots ,a_{n})\mapsto d}
を
- すべての
に対して
であり、
- すべての自然数
に対し、すべての
に対して
ならば
となる
ように定める[1][2][3][4]。
を
の最大公約数といい、
や
と表す。
が成り立つことを
が互いに素であると言う。
この定義から容易に次のことがわかる。
が成り立つ。
が成り立つ[2]。
- 最大公約数は存在すれば一意である[5]。
であれば(つまり空集合の)最大公約数は
である[2]。空積が
であることと空虚な真に注意せよ。
であれば
である。
とし、
と
の最大公約数は
である[1][6][7]。ゆえに、一般には最大公約数は最大の公約数ではない[8]。
とし、
でない自然数
と
の最大公約数は
である
自然数が一つ以下の場合は自明なので普通は二つ以上の場合を考えることになるが、二番目の性質により二つの自然数の最大公約数を考えることに帰着する。この定義からアプリオリ[9]には任意の二つの自然数に最大公約数が存在するかわからないが、実際には単に存在するだけでなく具体的に計算するアルゴリズムがユークリッドの互除法として知られており、この重要な応用がベズーの等式である。
たとえば
と
の最大公約数をユークリッドの互除法により求めてみよう。
なので
である。
なので
である。
なので
である。
なので
であり、最大公約数が
であることがわかった。
このように最大公約数の定義や計算に素数や素因数分解などのような高級な概念は全く必要ない[10]のだが、算術の基本定理が成り立つことを利用して最大公約数を明示的に表すこともできる。つまり、すべての素数から成る集合を
として、
を

と素因数分解すれば、次が成り立つ[11]。

たとえば
や
と素因数分解できるので、たしかに
となりユークリッドの互除法を用いて得られた値と一致する。
他にも次のような性質が知られている。
(ただし
は最小公倍数)が成り立つ[注釈 2]。この関係によって最小公倍数を計算するのが一般的である。
や
のような分配則が成り立つ。
(ただし
はオイラーのトーシェント関数)が成り立つ。
(ただし
はトマエ関数)が成り立つ。
- 正の奇数
と自然数
に対して
が成り立つ[12]。
(ただし
はラマヌジャン和(英語版))が成り立つ[13]。
が成り立つ[14]。
(ただし
は
の
進付値)が成り立つ。
特に重要な事実として、組
は半順序集合であるのでハッセ図を書くことができ、さらに
と
をそれぞれ結びと交わりとすれば完備分配束を成し[1]、
が最小元、
が最大元になる。したがって圏論的には
と
はそれぞれ余積と積に対応する。