【発展】ユークリッドの互除法の計算回数とフィボナッチ数列

【基本】ユークリッドの互除法の使い方 でユークリッドの互除法を用いた最大公約数の求め方を紹介しました。そこでは「小さい数字から順番に割っていくよりも早く求められる」と説明しましたが、「最長でどれくらいの計算回数が必要か」を、ここでは考えていきましょう。いきなり答えだけ書くと、計算回数は「小さい方の数の桁数の5倍以下」(ラメの定理)です。

途中で、数列や対数の知識を使います。

【広告】

「ユークリッドの互除法の計算回数」を考えるための準備

以下では、自然数 ab の最大公約数を考えていきます。なお、 $a\gt b$ としておきます。

さて、突然ですが、次のような数列を考えます。少し複雑ですが、「ユークリッドの互除法」で行う計算に、番号をつけていくだけです。

まず、 $r_0=a$、 $r_1=b$ とします。そして、 $n\geqq 2$ のとき、 $r_{n-2}$ を $r_{n-1}$ で割ったときの商を $q_{n-1}$、余りを $r_n$ とします。ただし、 $r_{n-1}=0$ の場合は、 $r_n=0$ とします。

つまり、こういうことですね。次の式が一番初めの式です。\[ r_0 = q_1 \cdot r_1 + r_2 \]これを進めて一般的に書くと、\[ r_{n-2} = q_{n-1} \cdot r_{n-1} + r_{n} \]と書けるようになります。

$r_{n-1}$ で割った余りが $r_n$ なので、数列 $\{r_n\}$ はどんどん小さくなっていきます。なので、いつかゼロになります。つまり、次のようになる自然数 N が存在するということですね。\[ r_{N-1} = q_{N} \cdot r_{N} \]このとき、N 回目の計算で、「ab の最大公約数は $r_N$」とわかることになります。なお、この数列は、$n \gt N$ のときは $r_n = 0$ となります。

このような数列を準備して、次に進みましょう。

一番回数が伸びるケース

ユークリッドの互除法の計算で、一番回数が伸びるケースを考えてみます。上の数列で言うと、N が大きくなるケース、ということですね。

数列 $\{r_n\}$ を考えてみると、\[ r_0 \gt r_1 \gt r_2 \gt \cdots \gt r_N \gt r_{N+1}= 0 \]となるので、 $r_n$ がなかなか減らないケースを考えればよさそうです。

上の数列の説明で書いた式をもう一度見てみます。\[ r_{n-2} = q_{n-1} \cdot r_{n-1} + r_{n} \]これで、 $r_n$ がなかなか減らないときというのは、 $q_{n-1}=1$ のときが考えられます。 $r_{n-2} \gt r_{n-1}$ なので、1回は割れてしまいますが、1回しか割れないなら余りの減少スピードは遅くなります。

つまり、一番計算回数が伸びてしまうケースというのは、\[ r_{n-2} = r_{n-1}+r_{n} \]のときだろうと、想像がつきます。これをよく見ると、次に紹介するフィボナッチ数列とよく似ていることがわかります。

【広告】

フィボナッチ数列との比較

「フィボナッチ数列」の定義を書いておきましょう。

フィボナッチ数列
$F_0=0, F_1=1$ とし、 $n\geqq 2$ に対して、\[ F_n = F_{n-1}+F_{n-2} \]で定義される数列 $\{F_n\}$ を、フィボナッチ数列という。

上に出てきた式 $r_{n-2} = r_{n-1}+r_{n}$ と比べると、添え字の順番が違うだけで式はよく似ていますね。「一番計算回数が伸びるケースは、フィボナッチ数列と関係がありそう」と書きましたが、それと関連して次のことを証明しましょう($\{r_n\}$ は余りの列、 $\{F_n\}$ はフィボナッチ数列です)。

フィボナッチ数列の性質
$n=1,2,\cdots,N$ のとき、\[r_{N+1-n} \geqq F_{n+1}\]が成り立つ。特に、 $b=r_1\geqq F_{N+1}$ が成り立つ。

証明を始める前に、このことから何がわかるのかを考えてみます。「最大公約数を求めよう」としたとき、フィボナッチ数列と比較して、仮に「$b\lt F_{20}$」ということが分かったとしましょう。このとき、「最大18回の計算で最大公約数が求められる」ということが分かるんですね。もし19回計算が必要なら、「$b\geqq F_{20}$」にならないといけないよ、と上の命題が教えてくれているわけです。

それでは、証明をしていきましょう。

証明
(1) $r_{N-1}\gt r_{N} \gt 0$ であり、ともに自然数なので、$r_{N}\geqq 1=F_2$ と $r_{N-1}\geqq 2=F_3$が成り立つ。

(2) kを2以上の自然数とする。$n=k$ のとき、$r_{N+1-k} \geqq F_{k+1}$ と $r_{N+2-k} \geqq F_{k}$ が成り立つとする。このとき、
\begin{eqnarray}
r_{N-k}
&=& q_{N-k+1} \cdot r_{N-k+1} + r_{N-k+2} \\[5pt] &\geqq& 1 \cdot F_{k+1} + F_k \\
&=& F_{k+2} \\
\end{eqnarray}となる。よって、$n=k+1$のときも成り立つ。

(1)(2)より、数学的帰納法から命題が成り立つことが示された。

(証明終)

このことから、計算回数を知りたければ、フィボナッチ数列との比較をすればいいということがわかります。しかし、「bとフィボナッチ数列とを比較する」というのは、少し不便です。もう少しわかりやすい表現ができないか考えてみましょう。

フィボナッチ数列の評価

上で、$b\geqq F_{N+1}$を示しましたが、フィボナッチ数列の$F_{N+1}$がいくらなのかはピンときません。もう少し比較しやすいように、この値がいくらくらいなのかを分かりやすくしたいですね。

フィボナッチ数列の一般項を具体的に書くことは可能ですが、次の形での評価の方がわかりやすいです。

フィボナッチ数列の性質
$\displaystyle \varphi = \frac{1+\sqrt{5}}{2}$ としたとき、自然数 n について、次が成り立つ。\[ F_{n+1} \geqq \varphi ^{n-1} \quad (※)\]
証明
(1) $n=1$のとき、$F_2=1$で、$\varphi^0=1$なので、(※)が成り立つ。

(2) $n=2$のとき、$F_3=2$である。また、\[ \varphi ^1 = \frac{1+\sqrt{5}}{2} \leqq \frac{1+\sqrt{9}}{2} = 2 \]なので、(※)が成り立つ。

(3) kを3以上の自然数とし、$F_{k+1} \geqq \varphi ^{k-1}$、$F_{k} \geqq \varphi ^{k-2}$が成り立つとする。

$\displaystyle \varphi = \frac{1+\sqrt{5}}{2}$ を変形して
\begin{eqnarray}
2\varphi &=& 1+\sqrt{5} \\
2\varphi -1 &=& \sqrt{5} \\
4\varphi^2 -4\varphi +1 &=& 5 \\
\varphi^2 &=& \varphi +1 \\
\end{eqnarray}が成り立つことに注意すると、
\begin{eqnarray}
F_{k+2}
&=&
F_{k+1}+F_{k} \\
& \geqq &
\varphi ^{k-1} +\varphi ^{k-2} \\
&=&
\varphi ^{k-2} (\varphi +1) \\
&=&
\varphi ^{k-2} \cdot \varphi ^2 \\
&=&
\varphi ^k \\
\end{eqnarray}が成り立つ。よって、$n=k+1$のときも(※)が成り立つ。

(1)(2)(3)より、すべての自然数nに対して、(※)が成り立つ。

(証明終)

ちなみに、$\displaystyle \varphi = \frac{1+\sqrt{5}}{2}$ は「黄金比」と呼ばれているものですね。

既に示した通り、$b\geqq F_{N+1}$ であり、さらに $F_{N+1} \geqq \varphi ^{N-1}$であることもわかったので、\[ b \geqq \varphi ^{N-1} \]が分かりますね。

ユークリッドの互除法の計算回数の評価

$b \geqq \varphi ^{N-1}$が得られましたが、右辺はまだ少しわかりづらいので、次のように変形してみます。

まず、両辺の常用対数を考えると、
\[ \log_{10} b \geqq (N-1) \log_{10} \varphi \]が得られます。ここで、関数電卓などを用いて(例えばGoogle電卓とかで)具体的に計算すると、\[ \log_{10} \varphi = \log_{10} \frac{1+\sqrt{5}}{2} = 0.2089\cdots \gt \frac{1}{5} \]であることがわかります。よって、
\begin{eqnarray}
\log_{10} b & \geqq & (N-1) \log_{10} \varphi \\
\log_{10} b & \gt & (N-1) \cdot \frac{1}{5} \\
5 \log_{10} b & \gt & N-1 \\
\end{eqnarray}がわかります。10進数で表したときのbの桁数をmとおけば、$m\gt \log_{10}b \geqq m-1$なので、$5m\gt N-1$が得られます。$m,N$は自然数なので、$5m\geqq N$がわかります。

以上から、次のことが分かります。

ラメの定理
a,bを自然数とし、小さい方の数の桁数をmとする。
このとき、ユークリッドの互除法を用いてab の最大公約数を求めるときの計算回数は、$5m$回以下となる。

例えば、「144と89の最大公約数」をユークリッドの互除法で求めるなら、89は2桁なので、10回以下の計算で求められるということですね。実際に計算してみると、次のようになります。
\begin{eqnarray}
1:\ & 144 &=& 1 \cdot 89 &+ 55 \\
2:\ & 89 &=& 1 \cdot 55 &+ 34 \\
3:\ & 55 &=& 1 \cdot 34 &+ 21 \\
4:\ & 34 &=& 1 \cdot 21 &+ 13 \\
5:\ & 21 &=& 1 \cdot 13 &+ 8 \\
6:\ & 13 &=& 1 \cdot 8 &+ 5 \\
7:\ & 8 &=& 1 \cdot 5 &+ 3 \\
8:\ & 5 &=& 1 \cdot 3 &+ 2 \\
9:\ & 3 &=& 1 \cdot 2 &+ 1 \\
10:\ & 2 &=& 2 \cdot 1 &\\
\end{eqnarray}これはなかなか余りが減っていかないケース、フィボナッチ数列のケースですね。

おわりに

ここでは、ユークリッドの互除法で計算回数がどの程度になるか、評価してみました。

小さい方から順番に割っていく方法の場合、何も工夫しなければ、最大で $\sqrt{b}$ 回の計算が必要です。b が数億の場合、数万回の計算が必要になってしまいます。実際には素数だけを考えればいいのですが、1万以下の素数でも1000個以上あるので、千回は計算しないといけません。

しかし、ユークリッドの互除法を使えば、数億の場合は桁数が9桁なので、45回以下の計算で必ず最大公約数が求まるんですね。ユークリッドの互除法は、大きな数の最大公約数を求めるときに計算が大幅に減ることがよくわかりますね。