ユークリッドの互除法

\(n=0\) の時は \(\mathrm{gcd}(m, n)=\mathrm{gcd}(m, 0)=m\) なので良い.

ここで, 整数 \(a, b\ (a\neq 0)\) に対して,
\(b\) を \(a\) で割った商を \(q\), 余りを \(r\ (0\leq r<|a|)\) とすると \(b=qa+r\).
\(d_1\) を \(b\) と \(a\) の公約数, \(d_2\) を \(a\) と \(r\) の公約数とする.
このとき, \(b=qa+r\) は \(d_2\) で割り切れるので \(d_2\) は \(b\) と \(a\) の公約数である.
また \(r=b-qa\) は \(d_1\) で割り切れるので \(d_1\) は \(a\) と \(r\) の公約数である.
よって「\(b\) と \(a\) の公約数の集合」と「\(a\) と \(r\) の公約数の集合」が一致するので \(\mathrm{gcd}(b, a)=\mathrm{gcd}(a, r)\).
これは 手順 2. において \(\mathrm{gcd}(m, n)=\mathrm{gcd}(n, r)\) を意味している.

\(n\neq 0\) の時, \(i\) 回目の手順 2. での \(n, r\) をそれぞれ \(n_i, r_i\) と置くと
\(r_1>r_2>\cdots>r_i\geq 0\) なので, \(r_k=0\) となる \(k\) が（必ず）存在する.
よって \(k\) 回目の手順 2. の後,
次の手順 3. で \(n_k\) を新たな \(m\), \(r_k=0\) を新たな \(n\) とみなすこととなり,
次の手順 1. で \(n=r_k=0\) より \(m=n_k\) を最大公約数として終了する.

また, 上の最大公約数に関する議論より
\(\mathrm{gcd}(m, n)=\mathrm{gcd}(n_1, r_1)=\cdots=\mathrm{gcd}(n_k, r_k)=\mathrm{gcd}(n_k, 0)=n_k\)
なので, 最大公約数を求められていることが分かる.