ユークリッドの互除法とは？計算例、なぜうまくいくか

どうも、木村（@kimu3_slime）です。

2つの整数に対してそれらの最大公約数が定まりますが、大きな数の最大公約数を地道に求めるのは結構難しいです。

今回は、最大公約数を求める方法のひとつとして、ユークリッドの互除法と呼ばれる方法と例、なぜうまいくかを紹介します。

ユークリッドの互除法とは、例
なぜうまくいくか
こちらもおすすめ

ユークリッドの互除法とは、例

整数\(a,b\)に対し、その最大公約数\(\mathrm{gcd}(a,b)\)を求めたいとしましょう。

ユークリッドの互除法（Euclidean algorithm）

\(a\geq b>0\)となると仮定する。除法の原理（整数の割り算）より、

\[ \begin{aligned}a = q_1 b +r_1\end{aligned} \]

となる\(q_1\)、\(0 \leq r_1 <b\)が存在します。

もし割り切れている\(r_1=0\)なら終了で、\(\mathrm{gcd}(a,b)=b\)です。

割り切れていない\(r_1 \neq 0\)ならば、再び除法の原理を\(b,r_1\)に対し適用して、

\[ \begin{aligned}b = q_2 r_1 +r_2\end{aligned} \]

となる\(q_2\)、\(0\leq r_2 <r_1\)が存在します。

\(r_2=0\)なら終了で、\(\mathrm{gcd}(a,b)=r_1\)です。

割り切れていないならば、先程と同様に除法の原理を繰り返し適用していきます。

いずれ余りは\(r_n =0\)となり、\(\mathrm{gcd}(a,b)= r_{n-1}\)となります。

最初に2つの数を割る。その余り\(r_1\)によって割った数\(b\)を割る。その余り\(r_2\)によって\(r_1\)を割る。こうして互いに除法を適用していくことで最大公約数が求まるので、互除法と呼ばれるわけです。

まずは、ユークリッドの互除法を試してみましょう。

\(\mathrm{gcd}(201,80)\)を求めたいとします。最初は\(a=201\)を\(b=80\)で割って、余り\(r_1\)を求めましょう。

\[ \begin{aligned}201 =2\cdot80 +41\end{aligned} \]

\(r_1 =41\)です。次のステップでは、前のステップの割る数\(b\)を前のステップの余り\(r_1\)で割ります。

\[ \begin{aligned}80 = 1\cdot 41 +39\end{aligned} \]

これを割り切れるまで繰り返すのが互除法です。

\[ \begin{aligned}41 = 1\cdot39+2\end{aligned} \]

\[ \begin{aligned}39= 19\cdot 2 +1\end{aligned} \]

\[ \begin{aligned}2= 1\cdot2 +0\end{aligned} \]

よって、\(\mathrm{gcd}(201,80)=1\)で、互いに素であることがわかりました。結局余りが1になるまで割り切れず、こういうケースは公約数が1しかないのです。2つの整数が互いに素であることの判定法としても使えますね。

別の例として、\(\mathrm{gcd}(2016,216)\)を求めてみましょう。

\[ \begin{aligned}2016 =9\cdot 216+72\end{aligned} \]

\[ \begin{aligned}216 = 3\cdot72+0\end{aligned} \]

よって、\(\mathrm{gcd}(2016,216)=72\)と求められました。

図的に捉えてみましょう。

最初は\(2016\)を\(216\)を基準に分けられないか考えます。しかしそれは割り切れず、余り\(r_1=72\)が出てきます。そこで次のステップでは\(72\)を基準に、ひとつ前の基準\(216\)を分けられないか考えます。すると、割り切れます\(216 =3 \times72 \)。よって、\(72\)を基準にすれば\(2016\)も\(216\)も割り切れることがわかるわけです。互除法の最初の式に結果を戻せば、\(2016 =9\cdot 216+72= 9\cdot 3\cdot72+72 =28 \cdot 72\)というわけですね。

この例から派生する問題として、\(\mathrm{gcd}(2016,216)=2016x+216y\)を満たす整数\(x,y\)を見つけられます。

そのためには、互除法の過程を逆にたどっていけば良いです。

\[ \begin{aligned}2016 =9\cdot 216+\mathrm{gcd}(2016,216)\end{aligned} \]

が成り立っているので、\(x=1,y=-9\)とすれば、

\[ \begin{aligned}2016 x +216 y =\mathrm{gcd}(2016,216)\end{aligned} \]

を満たします。今回は1段階で済みましたが、より多くの段階を踏んでいても互除法を逆にたどることで\(x,y\)を見つけることができます。

\(ax+by =\mathrm{gcd}(a,b)\)という方程式は、ベズーの等式（Bézout’s identity）、ベズー方程式として知られています。

なぜうまくいくか

ユークリッドの互除法は、なぜうまくいくのでしょうか。簡単な証明を与えましょう。

一般に、次の事実が成り立つのがポイントです。

\(a=qb+r\)のとき、\(\mathrm{gcd}(a,b)=\mathrm{gcd}(b,r)\)

これが成り立てば、互除法一つ一つのステップで、最大公約数の関係性が変わっていないことがわかります。したがって、

\[ \begin{aligned}\mathrm{gcd}(a,b)=\mathrm{gcd}(b,r_1)=\cdots \\= \mathrm{gcd}(r_{n-1},r_n)=\mathrm{gcd}(r_n,0)=r_n\end{aligned} \]

という等式が成り立つので、互除法はうまくいくのです。（\(0\)はすべての整数の倍数であり、すべての整数は\(0\)を割り切ります。特に\(r_n\)は\(0\)の約数です\(0 =0\cdot r_n\)。したがって、\(\mathrm{gcd}(r_n,0)=r_n\)です。）

では、\(a=qb+r\)のとき、\(\mathrm{gcd}(a,b)=\mathrm{gcd}(b,r)\)が成り立つことを確かめましょう。

\(d= \mathrm{gcd}(a,b)\)と置きます。最大公約数の定義より、\(d \mid a, d \mid b\)が成り立ちます。割り切ることの定義より、\(a = kd\),\(b= \ell d\)となる整数\(k,\ell\)が存在します。仮定より\(a=qb+r =q \ell d +r\)なので、\(r= (k-q)d\)です。\(k-q\)は整数なので、\(d \mid r\)であることが言えました。\(d\)は\(b,r\)の公約数です。

\(d\)が\(b,r\)の公約数の公約数のうち、最大のものであることを示しましょう。整数\(c\)を\(b,r\)の公約数、\(c\mid b, c \mid r\)とします。約数の定義より、\(b =mc, r=nc\)となる整数\(n,m\)が存在します。仮定より\(a=qb+r =(qm+n)c\)で、\(qm+n\)は整数なので、\(c\mid a\)です。つまり\(c\)は\(a,b\)の公約数であり、\(d\)は\(a,b\)の最大公約数であることから、\(c\leq d\)が成り立ちます。

よって、\(d\)が\(b,r\)の公約数のうち最大のものであることが確かめられたので、\(d=\mathrm{gcd}(b,r)\)が示せました。

以上、ユークリッドの互除法とは何か、その例と、なぜうまくいくか、その仕組みを紹介しました。

抽象代数学、代数的整数論では、整数\(\mathbb{Z}\)を一般化した環と呼ばれる集合を考えます。除法の原理が成り立つような環をユークリッド整域といい、そこではユークリッド互除法といった議論を同様に行うことができます。

整数の割り算（除法の原理）から最大公約数の定義、ユークリッドの互除法という流れは、シンプルながらもよくできていると思います。初等整数論の入り口として、ぜひ味わってみてください。

木村すらいむ（@kimu3_slime）でした。ではでは。