m 個の元 a_(1,n), ..., a_(m,n) の最大公約数を d_n ≧ 0 とする。

d_n = a_(1,n)b_1 + ... + a_(m,n)b_m となる有理整数
b_1, ..., b_n がある。これ等を具体的に求めるには Euclid の
互除法を使えばよい。

z_n = b_1y_1 + ... + b_my_m とおく。

z_n は N の元で x_1, ..., x_n の一次結合であらわしたとき
x_n の係数は d_n である。

d_n = 0 なら a_(1,n) = ... = a_(m,n) = 0 だから
N = <y_1, ..., y_m> ⊂ [x_1, ..., x_(n-1)] である。

d_n ≠ 0 と仮定する。
a_(i,n) = d_n q_i とする。
y_i - q_iz_n の x_n の係数は 0 である。

一方、
N = <y_1, ..., y_m> = <y_1, ..., y_m, z_n>
= <y_1 - q_iz_n, ..., y_m - q_mz_n, z_n>

よって
L = <y_1 - q_iz_n, ..., y_m - q_mz_n> とおくと、
N = L + Z(z_n) である。

L は [x_1, ..., x_(n-1)] に含まれる。
この L と [x_1, ..., x_(n-1)] に上記と同様の手続きを行う。

最終的に、N = <z_1, ..., z_n> となる。
z_1, ..., z_n のなかで 0 となるものを省けば N の基底が得られる。