Notes_JP

あまり知られていないこと

ユークリッドの互除法

ユークリッドの互除法は,整数$a$と$b$の最大公約数を求める方法です.

今,$a>b>0$としましょう.
$a$を$b$で割った時の商を$q_1$, 余りを$r_1$とすると,
\begin{align}
a=bq_1+r_1 \qquad(0\leq r_1< b )
\end{align}
と書くことができます.
よって,以下のことがわかります:

  1. $a$と$b$の公約数は,$r$の約数でもなければいけません.
  2. $b$と$r_1$の公約数は,$a$の約数でもあります.

従って,「$a$と$b$の最大公約数」=「$b$と$r_1$の最大公約数」であることがわかりました.

この手順を$b>r_0>0$に適用し,繰り返せば,$i$回目の余り$r_i\geq0$は単調に減少していくため,いつかは$0$になります.これを$N$回目であるとすれば,
\begin{align}
r_{N-2}=r_{N-1}q_N
\end{align}
となり,$a$と$b$の最大公約数$r_{N-1}$が求まります.
(但し,$r_{-1}=a$, $r_{0}=b$とします.)