最大公約数を求める有名なアルゴリズムであるユークリッドの互除法を紹介します。
ユークリッドの互除法
2つの整数 \(m, n\) に対して, 以下の手続きを行う事で最大公約数を得られる.
- \(n=0\) ならば \(m\) を最大公約数として終了する.
- \(m\) を \(n\) で割り, その余りを \(r\ (0\leq r<|n|)\) とする.
- \(n\) を新たな \(m\), \(r\) を新たな \(n\) とみなし, 1. に戻る.
証明
\(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\)
なので, 最大公約数を求められていることが分かる.
最大公約数は素因数分解して求めることも出来ます。
しかし、一般的に素因数分解するのは難しく、ユークリッドの互除法の方が簡単に求められます。
例
\(2022\) と \(108\) の最大公約数をユークリッドの互除法を用いて求めてみましょう.
\[
\begin{array}{ccccccc}
2022&=&18&\times&108&+&78\\
108&=&1&\times&78&+&30\\
78&=&2&\times&30&+&18\\
30&=&1&\times&18&+&12\\
18&=&1&\times&12&+&6\\
12&=&1&\times&6&+&0
\end{array}
\]
となり、\(2022\) と \(108\) の最大公約数が \(6\) であることが分かります。
\(117\) と \(-12\) の最大公約数をユークリッドの互除法を用いて求めてみましょう.
\[
\begin{array}{ccccccc}
117&=&(-9)&\times&(-12)&+&9\\
-12&=&(-2)&\times&9&+&6\\
9&=&1&\times&6&+&3\\
6&=&2&\times&3&+&0
\end{array}
\]
となり、\(117\) と \(-12\) の最大公約数が \(3\) であることが分かります。
コメント