ユークリッドの互除法は、2つの自然数の最大公約数を求める手法です。
自然数について、をで割った余りをとするとき、すなわち
\begin{equation}
a = qb + r \tag{1}
\end{equation}が成り立つとき、
\begin{equation}
\mathrm{gcm}(a,b) = \mathrm{gcm}(b,r)
\end{equation}が成り立つ。
(ここでgcmはの最大公約数を表す。)
という関係を繰り返し用いていくと、最大公約数を求めることができるというものです。
本稿では、式(1)の関係が成り立つときに
\begin{equation}
\mathrm{gcm}(a,b) = \mathrm{gcm}(b,r)
\end{equation}が成り立つことを証明していきます。
まず、の公約数をとし、
\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}となります。
つまり、の公約数はの約数でもあることが分かります。
したがって、の公約数であっての公約数でないものが存在する可能性を考慮して、
\begin{equation}
\mathrm{gcm}(a,b) \leqq \mathrm{gcm}(b,r) \tag{2}
\end{equation}が成り立ちます。
逆に、の公約数をとし、
\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}となります。
つまり、の公約数はの約数でもあります。
したがって、の公約数であっての公約数でないものが存在する可能性を考慮して、
\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}が成り立つことが分かります。