数式で独楽する

数式を使って楽しむブログです

[tex: ]

ユークリッドの互除法

ユークリッドの互除法は、2つの自然数の最大公約数を求める手法です。

自然数 a,b \ (a \leqq b)について、 a bで割った余りを rとするとき、すなわち

\begin{equation}
a = qb + r \tag{1}
\end{equation}が成り立つとき、
\begin{equation}
\mathrm{gcm}(a,b) = \mathrm{gcm}(b,r)
\end{equation}が成り立つ。
(ここでgcm (x,y) x,yの最大公約数を表す。)

という関係を繰り返し用いていくと、最大公約数を求めることができるというものです。

本稿では、式(1)の関係が成り立つときに
\begin{equation}
\mathrm{gcm}(a,b) = \mathrm{gcm}(b,r)
\end{equation}が成り立つことを証明していきます。

まず、 a,bの公約数を m_1とし、
\begin{eqnarray}
a &=& a_1 m_1 \\
b &=& b_1 m_1
\end{eqnarray}と置きます。
式(1)に代入すると、
\begin{eqnarray}
a_1 m_1 &=& qb_1 m_1 + r \\
\therefore \ r &=& (a_1 - qb_1)m_1
\end{eqnarray}となります。
つまり、 a,bの公約数は rの約数でもあることが分かります。
したがって、 b,rの公約数であって a,bの公約数でないものが存在する可能性を考慮して、
\begin{equation}
\mathrm{gcm}(a,b) \leqq \mathrm{gcm}(b,r) \tag{2}
\end{equation}が成り立ちます。

逆に、 b,rの公約数を m_2とし、
\begin{eqnarray}
b &=& b_2 m_2 \\
r &=& r_2 m_2
\end{eqnarray}と置きます。
式(1)に代入すると、
\begin{eqnarray}
a &=& qb_2 m_2 + r_2 m_2 \\
\therefore \ a &=& (qb_2 + r_2)m_2
\end{eqnarray}となります。
つまり、 b,rの公約数は aの約数でもあります。
したがって、 a,bの公約数であって b,rの公約数でないものが存在する可能性を考慮して、
\begin{equation}
\mathrm{gcm}(a,b) \geqq \mathrm{gcm}(b,r) \tag{3}
\end{equation}が成り立ちます。

式(2), (3)より、
\begin{equation}
\mathrm{gcm}(a,b) = \mathrm{gcm}(b,r)
\end{equation}が成り立つことが分かります。