gcm(a_1, a_2, ........., a_n) = d である。 a_{1}x_{1} + ......... + a_{n}x_{n}と表せる形の整数の集合 I を考える。 I = { x ∈ Z : 或る x_{1}, ........, x_{n} が存在して n = a_{1}x_{1} + ......... + a_{n}x_{n} } x ∈ I ならば x の倍数 nx も I の要素であり、またx, y ∈ I ならば x ± y ∈ I となる。 よって I の要素の絶対値のうち最小のものを e とすると I は e の倍数の集合となることがわかる。 （∵ e' = ne + e'' , 0 ＜ e'' ＜ e とすると e'' ∈ I となり矛盾する。） 或る x_1, ........, x_n が存在して e = a_1x_1 + ......... + a_nx_n だから e は d の倍数。 また a_i は I に含まれるので、逆に a_i は e の倍数。よって e は a_1, ........., a_n の公約数。 よって e = d。つまり d は a_{1}x_{1} + ......... + a_{n}x_{n} の形に表すことが出来る。 quod erat demonstrandum.
