本記事は数学の徹底解説シリーズに含まれます。
初学者の分かりやすさを優先するため，多少正確でない表現が混在することがあります。もし致命的な間違いがあればご指摘いただけると助かります。
目次
ユークリッドの互除法
自然数$a,b$に対して，割り算の繰り返し操作を考える。
\begin{align}
a &= q_{1}b+r_{1}\\[0.7em]
b &= q_{2}r_{1}+r_{2}\\[0.7em]
r_{1} &= q_{3}r_{2}+r_{3}\\[0.7em]
&\vdots\notag\\[0.7em]
r_{i-2} &= q_{i}r_{i-1}+r_{i}\\[0.7em]
&\vdots\notag
\end{align}
a &= q_{1}b+r_{1}\\[0.7em]
b &= q_{2}r_{1}+r_{2}\\[0.7em]
r_{1} &= q_{3}r_{2}+r_{3}\\[0.7em]
&\vdots\notag\\[0.7em]
r_{i-2} &= q_{i}r_{i-1}+r_{i}\\[0.7em]
&\vdots\notag
\end{align}
このとき$r_{n+1}=0$となる$n$が存在し，
\begin{align}
\gcd (a,b) &= r_{n}
\end{align}
\gcd (a,b) &= r_{n}
\end{align}
となる。すなわち，$r_{n}$は$a$と$b$の最大公約数となる。
ユークリッドの互除法の肝は，素因数分解を行わなくても二つの整数の最大公約数を求めることができるアルゴリズムを確立した点にあります。このアルゴリズムは，紀元前300年頃にユークリッドによって書かれたとされている「ユークリッド原論」で記述されています。
証明
余りの性質から
\begin{align}
b > r_{1} > r_{2} > \cdots > r_{i} > \cdots
\end{align}
b > r_{1} > r_{2} > \cdots > r_{i} > \cdots
\end{align}
となるため，$r_{n+1}=0$となる$n$が存在します。すると，最大公約数と除算の余りの関係より，
\begin{align}
\gcd (a, b) = \gcd (b. r_{1}) = \gcd (r_{1}, r_{2}) = \cdots = \gcd (r_{n-1}, r_{n}) = \gcd (r_{n}, 0) = r_{n}
\end{align}
\gcd (a, b) = \gcd (b. r_{1}) = \gcd (r_{1}, r_{2}) = \cdots = \gcd (r_{n-1}, r_{n}) = \gcd (r_{n}, 0) = r_{n}
\end{align}
が得られます。
コメント