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

🕒 2016/05/02 🔄 2023/05/01

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

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

📘 目次

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

以下では、自然数 a と b の最大公約数を考えていきます。なお、 $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 回目の計算で、「a と b の最大公約数は $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とする。このとき、ユークリッドの互除法を用いてaとb の最大公約数を求めるときの計算回数は、$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}これはなかなか余りが減っていかないケース、フィボナッチ数列のケースですね。