ユークリッドの互除法について

ユークリッドの互除法という言葉は高校生の時に耳にしたことがあります。

しかし、当時は受験生でユークリッドの互除法に興味はありつつも、なんか発展的な内容だしそこまで手が回らないなぁと思ってそのままにしていました。

以前にピタゴラス数の求め方という記事を書きました。

ピタゴラス数の求め方は中学生の時に疑問に思ったことがあり、長い年月を経て数論を勉強し始めたことで解決しました。

今回のユークリッドの互除法は高校生の時にわからなかったことなので、なんだか数論を勉強することで自分の人生を振り返っているような錯覚があります笑

それではユークリッドの互除法について書いていきます。

説明の前に

説明に入る前に用語の確認をしておきます。

割り切れる

\(a,b\) を \(0\) でない整数とする時、 \(a\) が \(b\) で割り切れるとは、 \(a\) が \(b\) の倍数であることを意味します。

\(a\) が \(b\) の倍数であるということは、ある整数 \(k\) を用いて \(a=kb\) と表せることです。

余り

\(a\) を \(b\) で割ったときの商を \(q\) 、余りを \(r\) とすると、

\(a = b \times q + r\)

\(0\le r\lt b\) です。

因数

ある整数 \(a\) について、 \(a\) を割る数は \(a\) の因数といいます。

例えば、 \(12\) の因数は \(1,2,3,4,6,12\) です。

また、ある整数 \(a,b\) について、その両方を割る整数を \(a,b\) の共通因数といいます。

最大公約数

ある整数 \(a,b\) をともに割る整数を \(a,b\) の共通因数と言いましたが、 \(a,b\) の公約数という呼び方もします。

というわけで \(a,b\) の最大公約数は文字通り最大の公約数、共通因数となります。

また、 \(a\gt b\) として \(a\) を \(b\) が割る時、 \(b\) は \(b = b \times 1\)より \(b\) を割るため 、 \(b\) が \(a,b\) の共通因数になります。

ここで、 \(a,b\) の最大公約数は \(a,b\) をともに割り切ることから \(g\) とすると、 \(1\le g\le b\) となります。

取りうる最大の共通因数が \(b\) となるので、 \(a\) を \(b\) が割る時 \(b\) が最大公約数となります。

また、 \(a,b\) の最大公約数が \(1\) のときは、共通因数がないので互いに素といいます。

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

ユークリッドの互除法とは2つの整数 \(a\) と \(b\) の最大公約数を素早く求める一連の操作を指します。

いちいち \(a\) と \(b\) の最大公約数とかくと文字数が増えるので、 \(gcd(a,b)\) で表します。
(gcd: greatest common divisorで最大公約数を意味しています)

どのような操作かというと、 \(a>b\) として考えていきますが、まず \(a\) を \(b\) で割った余り \(r_0\) を求めます。

次に \(b\) を \(r_0\) で割った余り \(r_1\) を求めます。

その次に \(r_0\) を \(r_1\) で割った余り \(r_2\) を…というように割り切れるまで続けていきます。

\(r_{n-2}\) を \(r_{n-1}\) で割った余り \(r_{n}\) について、仮に \(r_{n-1}\) を \(r_{n}\) で割ったときに割り切れたとしたら、割り切れる直前の余りである \(r_{n}\) が \(gcd(a,b)\) になります。

ちがう言い方をしたら割り切ったときの割る数が最大公約数になる感じです。

式で表すとこんな感じになります。 \(q_i\) を商として、

\(\begin{aligned} a&=b\times{q_0}+r_0\\ b&=r_{0}\times{q_1}+r_1\\ r_0&=r_{1}\times{q_2}+r_2\\ \vdots\\r_{n-2}&=r_{n-1}\times{q_n}+r_n\\r_{n-1}&=r_{n}\times{q_{n+1}}\end{aligned}\)

となるとき、

\(gcd(a,b)=r_n\) となります。

これだけだと分かりづらいと思うので、まずは例として \(gcd(56, 24)\) を求めてみます。

\(\begin{aligned}56&=24\times{2}+8\\24&=8\times{3}+0\end{aligned}\)

\(gcd(56,24)=8\)

これだと素因数分解で最大公約数を求めても良かったような気もしますが、桁数が増えてくると素因数分解では限界が来ると思います。

そんなときにユークリッドの互除法が役に立つことになります。

それなら試してみましょうということで、 \(gcd(11675849,4765)\) を求めてみようと思います(白目)

\(\begin{aligned}11675849&=4765\times{2450}+1599\\4765&=1599\times{2}+1567\\1599&=1567\times{1}+32\\1567&=32\times{48}+31\\32&=31\times{1}+1\\31&=1\times{31}+0\end{aligned}\)

\(gcd(11675849,4765)=1\)

とまぁ、こんなかんじで桁数が大きくなっても数回の操作で最大公約数を求めることができました。

この操作でなんかよくわからないけど最大公約数が求まるらしいということはわかったと思いますので、次はどうして求まるのかという部分について説明したいと思います。

どうして最大公約数が求まるのか

aとbの最大公約数はbと余りrの最大公約数と同じになる

ふたつの \(0\) でない整数 \(a,b (a \gt b )\) について、 \(gcd(a,b)=g\) とする。

\(q\) を商、\(r\) を余りとして、

\(a = b \times q + r\)

と表すことができます。

ここで、 \(gcd(a,b)=g\) より、適当な整数 \(a^{\prime}, b^{\prime}\) を用いて、\(a=ga^{\prime}, b = gb^{\prime}\) と表せることから、

\(\begin{aligned}a&=b\times q + r \\ r &= a – bq \\ r &= ga^{\prime} – gb^{\prime}q \\ r &= g(a^{\prime}-b^{\prime}q)\end{aligned}\)

となります。

\(r\) が \(g\) の倍数となるため、 \(gcd(a,b)=g\) は\(r\) を割ります。

つまり、 \(a,b\) の最大公約数 \(g\) は \(b,r\) の共通因数になります。

ここまでだと \(g\) が \(b,r\) の共通因数であることは言えますが、 \(b,r\) の最大公約数となるかはわかりません。

そこで、 \(gcd(b,r)=g^{\prime}\) とおいて、それが \(g\) と一致することを確かめます。

適当な整数 \(b^{\prime}, r^{\prime}\) を用いて (\(b^{\prime}\) はさっき使ったのと無関係だと思ってください)、 \(b=g^{\prime}b^{\prime}, r=g^{\prime}r^{\prime}\) と表せることから、

\(\begin{aligned}a&=b \times q + r \\ a&=g^{\prime}b^{\prime}q + g^{\prime}r^{\prime}\\ a&= g^{\prime}(b^{\prime}q+r^{\prime})\end{aligned}\)

となります。

よって、 \(a\) は \(g^{\prime}\) の倍数となるので、因数に \(g^{\prime}\) を持ちます。

ここで、 \(g \lt g^{\prime}\) と仮定すると、 \(a,b\) ともに \(g^{\prime}\) を因数に持つため、最大公約数の \(g\) より大きい数を共通因数として持つので \(gcd(a,b)=g\) と矛盾します。

よって、 \(g^{\prime} \le g\) となります。

つぎに、 \(g^{\prime} \lt g\) と仮定すると、 \(b,r\) ともに \(g\) を因数に持つため、最大公約数の \(g^{\prime}\) よりも大きい数を共通因数として持つので \(gcd(b,r)=g^{\prime}\) と矛盾します。

よって、 \(g \le g^{\prime}\) となります。

2つの結果から \(g = g^{\prime}\) となることがわかります。

よって、

\(a = bq + r\)

において、

\(gcd(a,b) = gcd(b,r)\)

となります。

割り切ったときの割る数が最大公約数となる

割られる数 \(a\) と割る数 \(b\) 、そして余り \(r\) の間にある最大公約数の関係がわかったので、次はどうしてユークリッドの互除法の操作を繰り返していくと最大公約数が求まるのか説明します。

\(\begin{aligned} a&=b\times{q_0}+r_0\\ b&=r_{0}\times{q_1}+r_1\\ r_0&=r_{1}\times{q_2}+r_2\\ \vdots\\r_{n-2}&=r_{n-1}\times{q_n}+r_n\\r_{n-1}&=r_{n}\times{q_{n+1}}\end{aligned}\)

すでに登場したこの式において、第一行の式より、

\(gcd(a,b)=gcd(b,r_0)\) です。

次に第二行の式より、

\(gcd(b,r_0)=gcd(r_0,r_1)\) です。

そして、第三行の式より、

\(gcd(r_0,r_1)=gcd(r_1,r_2)\) となります。

\(gcd(r_{i-2},r_{i-1})=gcd(r_{i-1},r_i)\) となるので、

\(gcd(a,b)=gcd(r_{n-1},r_n)\)

となります。

ここで、 \(r_{n-1}\)は\(r_n\) で割れるため、 \(gcd(r_{n-1},r_n)=r_n\) となります。

よって、割り切ったときの割る数、割り切る直前の割り算の余りである \(r_n\) が\(gcd(a,b)\) となります。

ユークリッドの互除法は常に終了するのか

ユークリッドの互除法は常に使える方法なのかということについても触れておこうと思います。

ユークリッドの互除法を繰り返していって、どこかで割り切れたら最大公約数が求まるということはわかりました。

ココで1つ疑問が生まれます。

はい、どこかで必ず割り切れます。

それでは、余り\(r_i\)の変化をいきましょう。

ふたたびこの式を見ていきます。

\(\begin{aligned} a&=b\times{q_0}+r_0\\ b&=r_{0}\times{q_1}+r_1\\ r_0&=r_{1}\times{q_2}+r_2\\ \vdots\\r_{n-2}&=r_{n-1}\times{q_n}+r_n\\r_{n-1}&=r_{n}\times{q_{n+1}}\end{aligned}\)

まず第一行をみていきます。

\(r_0\)は\(b\)で割ったときの余りですので、\(0 \le r_0 \lt b\)です。

次に、第二行をみていきます。

\(b,r_0\)をスライドさせたような式になっていますが、\(r_1\)は\(r_0\)で割った余りですので、\(0 \le r_1 \lt r_0\)です。

第三行をみてみると、\(r_2\)は\(r_1\)で割った余りですので、\(0 \le r_2 \lt r_1 \lt r_0\)です。

この操作を繰り返していくとわかるのが、余り\(r_i\)は単調減少していて、

\(0 \le \dots \lt r_i \lt r_{i-1} \lt r_{i-2} \lt \dots \lt r_2 \lt r_1 \lt r_0\)

のようになります。

よって、必ずどこかで余りは\(0\)になります。

そして、そこでユークリッドの互除法は終了します。