ユークリッドの互除法 最大公約数を求める方法

　ユークリッドの互除法とは、2つの整数の最大公約数を見つけるための方法で、以下の手順で見つけます。

整数$A$と$B$の最大公約数を見つけるには、

1.  $A$と$B$の大きい方を小さい方で割り、余り$r_1$を求めます。
2.  $A$か$B$の割る数になった方を$r_1$で割り、余り$r_2$を求めます。

2.のように割る数を余りで割ることを繰り返し、余りが$0$になったときの割る数が$A$と$B$の最大公約数となります。

　例として$168$と$792$の最大公約数を求めてみます。

まずは$792\div168$を計算すると

$$792\div168=4\ 余り120$$

となります。

次は割る数の$168$を余りの$120$で割って

$$168\div120=1\ 余り48$$
となります。

割る数を余りで割ることを繰り返すと

$$\begin{align*}120\div48&=2\ 余り24\\[1em]48\div24&=2\ 余り0\end{align*}$$

$24$で割ったとき余りが$0$になるので$168$と$792$の最大公約数は$24$であるとわかります。

　おおまかな最大公約数が求められる仕組みは以下のようになります。

　整数$A$と$B$の最大公約数を$G$とすると、

$$\begin{equation}A=Ga,\ B=Gb\quad(a,b:互いに素な整数)\end{equation}$$

となります。
$A$を$B$で割ったとき、商が$k_1$、余りが$r_1$であったとすると
$$A=Bk_1+r_1$$
と書くことができ、$(1)$より左辺が$G$の倍数ならば右辺も$G$の倍数でなければならないこと、$B$が$G$の倍数であることから$r_1$もまた$G$の倍数であることがわかります。
また、$B$で割ったときの余りなので$0\leqq r_1<|B|$となります。

関連：互いに素とは？

　次に$B$を$r_1$で割ったときのことを考えると、商が$k_2$、余りが$r_2$であるとすると

$$B=r_1k_2+r_2$$

となり、上記より$B$と$r_1$は$G$の倍数なので、$r_2$もまた$G$の倍数ということになります。

また、$r_1$で割ったときの余りなので$0\leqq r_2<r_1$となります。

　このことから互除法の手順を繰り返すと余りは$G$の倍数かつ前の手順による割り算の余りより小さい（ただし、$0$以上の）整数となるので、いずれ余りは$0$になります。
$n$回目の余り$r_n$で$0$になったとすると、このときの割る数は1つ前の手順での割り算での余り$r_{n-1}$でこれが最大公約数$G$となります。

　ここで最大公約数以外で割り切れてしまうことはないのか？と思うかもしれませんが、最大公約数でしか割り切れないことは以下のように確かめることができます。

　上記と同じような流れで整数$A$と$B$の最大公約数を$G$として、$A$を$B$で割ったときの商が$k$、余りが$r$であったとすると$(1)$より

$$\begin{align*}A&=Bk+r\tag{*}\\[0.5em]r&=Bk-A\\[0.5em]&=G(bk-a)\end{align*}$$

となり、余り$r$は$G$の倍数、すなわち$G$を約数に持つことがわかります。
このことから$G$は$A,B,r$の公約数であることがわかります。

　次に$B$と$r$の最大公約数を$G$以外の整数$G'$であると考えると、$(1)$のように

$$B=G'b',\ r=Gr'\quad(b',r':互いに素な整数)$$

と書くことができます。これを$(*)$に代入すると

$$A=G'b'k+G'r'=G'(b'k+r')$$

となり、$G'$は$A$の約数でもあるから、$G'$もまた$A,B,r$の公約数であることがわかります。

ここで、$G$と$G'$について$G>G'$であるとすると、$G'$は$B$と$r$の最大公約数であるにも関わらず、より大きい$G$という公約数があるということになり矛盾します。
今度は$G<G'$であるとすると、$G$は$A$と$B$の最大公約数であるにも関わらず、より大きい$G'$という公約数があるということになり矛盾します。

したがって、$G\neq G'$という仮定が間違っていることより$G=G'$であり、$G$は$A,B,r$の最大公約数であるということがわかります。

　この結論を互除法で登場したすべての割り算に対して適用すれば、$0$である$r_n$を除く$A,B,r_1,r_2,\cdots,r_{n-1}$の最大公約数は$G$なので、$G$より大きい数で割り切れることはなく、また$r_1,r_2,\cdots,r_{n-1}$は$G$の倍数なので$G$より小さい数はそもそも登場しないため、互除法で余りが$0$になるのは必ず割る数$r_{n-1}$が$G$のときであることがわかります。