最大公約数

任意の \((a_1, a_2, \ldots, a_n)\in\mathbf{Z}^n\) に対して, 上記の条件1,2 を満たす自然数 \(g\) がただ１つ存在すること
(存在と一意性)を示す.
条件1,2 は

1. 任意の \(a\in \{a_1,\ldots,a_n\}\) に対して \(g\mid a\).
2. 整数 \(d\) が 任意の \(a\in \{a_1,\ldots,a_n\}\) に対して \(d\mid a\) ならば \(d\mid g\).

と同値である.

[\(n=0\) のとき]
\(\mathrm{gcd}\ :\ \{\emptyset\}\rightarrow\mathbf{N}\) を考える事となり, 条件 1,2 は

1. 任意の \(a\in\emptyset\) に対して \(g\mid a\).
2. 整数 \(d\) が 任意の \(a\in\emptyset\) に対して \(d\mid a\) ならば \(d\mid g\).

となるが, 条件1は常に真である.
また, 条件2の「任意の \(a\in\emptyset\) に対して \(d\mid a\)」の部分が常に真なので, 任意の整数 \(d\) に対して条件2は真でなければならない. つまり自然数 \(g\) は任意の整数 \(d\) に対して \(d\mid g\) を満たす. そのような \(g\) は \(g=0\) のみ. (存在と一意性)
ゆえに \(n=0\) のとき \(\mathrm{gcd}()=0\).

[\(n\geq 1\) のとき]
\(a_1, a_2, \ldots, a_n\) に対して \(a_i\neq 0\) となる \(i\) が存在するとき,
整数 \(a\) の正の約数を \(D(a)\) と書き, \(D=\displaystyle\bigcap_{i=1}^nD(a_i)\) とすると,
\(a_i\neq 0\) となる \(i\) に対して \(D(a_i)\) は有限集合なので \(D\) も有限集合である.
また, 任意の \(1\leq i\leq n\) に対して \(1\in D(a_i)\) であることより, \(D\neq\emptyset\) である.
ここで \(g=\max D\) と置くと, \(g\) が条件1を満たすのは明らか.
整数 \(d\) が 任意の \(1\leq i\leq n\) に対して \(d\mid a_i\) を満たすとすると,
\(|d|\mid a_i\) でもあるので \(|d|\in D(a_i)\). ゆえに \(|d|\in D\).
このとき, \(g\geq|m|\) であるが, \(l=\mathrm{lcm}(g, |d|)\) と置くと, (最小公倍数)
任意の \(1\leq i\leq n\) に対して \(g\mid a_i, |d|\mid a_i\) なので \(l\mid a_i\).
よって \(l\in D\) となり \(l\leq g\). しかし \(l\geq g\) でもあるので \(l=g\).
ゆえに \(|d|\mid g\) となるので \(d\mid g\).
これは \(g\) が条件２を満たすことを示している.(存在)
ここで, 自然数 \(g^\prime\) が条件1,2 を満たすとすると,
\(g\) に対する条件1 と \(g^\prime\) に対する条件2 より \(g\mid g^\prime\).
\(g^\prime\) に対する条件1 と \(g\) に対する条件2 より \(g^\prime\mid g\).
\(g, g^\prime\) は共に自然数なので \(g=g^\prime\). (一意性)

\(a_1=\cdots=a_n=0\) のとき,
任意の整数 \(d\) に対して \(d\mid 0\) なので, 条件２より \(g\) は任意の整数 \(d\) に対して \(d\mid g\) を満たす.
任意の整数で割り切れる整数は \(0\) のみなので \(g=0\) であり, これは条件１も満たす.(存在と一意性)

以上より, 任意の \((a_1, a_2, \ldots, a_n)\in\mathbf{Z}^n\) に対して示された.