整数全体の集合を Z と書きます。
Z には2つの演算、加法 a + b、乗法 ab があり、
Z は乗法の単位元 1 をもつので、 単位元をもつ環であり、 1 = 0 ではないので、零環ではなく、 乗法について可換であるので、可換環 であり、 0 以外の零因子 をもたないので、整域となります。
自然数全体の集合(0 を含む)を N と書きます。 N の元 x、y (y は 0 ではない)に対して x = qy + r、r < y となる N の元 q、r が存在します。
Z - { 0 } から N への写像 N を、 N(x) は x の絶対値として定義すると、 Z の元 x、y (y は 0 ではない)に対して x = qy + r、r = 0 または N(r) < N(y) となる Z の元 q、r が存在するので、Z は ユークリッド整域となります。
よって Z の元 x、y に対して、
| g(x, y) | = | x | (y = 0 のとき) | (1) |
| g(y, r) | (y = 0 でないとき、r は x = qy + r を満たす元) | (2) |
Z の元 x、y に対して、q、r を x = qy + r となる Z の元とすると、 x は y、r で生成される Z の イデアル (y, r) に含まれます。 また、r は (x, y) に含まれるので、(x, y) = (y, r) となります。 よって、g(x, y) の定義の (1) のとき (x, y) = (x) = (g(x, y))、 (2) のとき (x, y) = (y, r) となるので、 (x, y) = (g(x, y)) となります。 よって、x、y は (g(x, y)) に含まれるので、g(x, y) の倍数になります。 また、g(x, y) = ax + by となる Z の元 a、b が存在するので、 x = de、y = df ならば g(x, y) = (ae + bf)d となって、 g(x, y) は x と y のすべての公約数の倍数になっているので、 g(x, y) は x と y の最大公約数 (最大公約元) となります。