フィボナッチ数列で互除法っぽいこと
Mathlogの記事を上からばーっと見ていたのですが，フィボナッチ数に関する話題が既にいくつか挙がっていました。せっかくなので僕もあやかって，フィボナッチ数についての性質として フィボナッチ数列で互除法を考えられる ことを述べていきます。
この記事の目標
改めてフィボナッチ数列の定義を述べます。
数列$\suuretu{F_n}$を，次の漸化式で定める。$$ F_1=F_2=1,\quad F_{n+2}=F_{n+1}+F_n\quad (n=1,2,\dots) $$この数列をフィボナッチ数列$\textrm{(fibonacci sequence)}$と呼ぶ。
そして，この記事の目標は次の定理です。なお，正の整数$a,\ b$に対して，$a$と$b$の最大公約数を$\gcd(a,\ b)$と書かせてください。例えば$\gcd(24,56)=8$などです。
$n,\ m$を自然数とする。$\gcd(n,\ m)=a$としたとき，$$ \gcd\left(F_n,\ F_m\right)=F_a $$が成り立つ。
証明に向けて
やはりいくつか性質を見ていきながら，定理１が正しいことを見ていきます。ここではいくつか準備をします。
$m,\ n$は$1< m< n$を満たす自然数とする。このとき次が成り立つ。$$ F_n=F_m\cdot F_{n-m+1}+F_{m-1}\cdot F_{n-m} $$
$m=2$とする。この時示す式は$$ F_n=F_2\cdot F_{n-1}+F_{1}\cdot F_{n-2} $$だが，フィボナッチ数列の定義から，この等式は正しい。
$m=k$の時に示すべき式が正しいとする。$m=k+1$のとき，次のように変形できる。$$ \begin{align} &\ F_{(k+1)}\cdot F_{n-(k+1)+1}+F_{(k+1)-1}\cdot F_{n-(k+1)}&&\\ =&\ F_{k+1}\cdot F_{n-k}+F_{k}\cdot {F_{n-k-1}} &&\\ =&\ F_{k+1}\cdot F_{n-k}+F_{k}\cdot {(F_{n-k+1}-F_{n-k})} &&\because \textbf{漸化式}\\ =&\ F_{k-1}\cdot F_{n-k}+{F_k\cdot F_{n-k+1}}-F_k\cdot F_{n-k} && \\ =&\ F_{k+1}\cdot F_{n-k}+{(F_n-F_{k-1}\cdot F_{n-k})}-F_k\cdot F_{n-k} \ \ \ &&\because \textbf{帰納法の仮定} \\ =&\ F_n+{(F_{k+1}-F_k-F_{k-1})}F_{n-k} && \\ =&\ F_n && \because F_{k-1}+F_{k}=F_{k+1} \end{align} $$よって$m=k+1$のときも，示すべき式が正しいことが分かった。◆
この補題から，例えば$F_{2n+1}={F_{n}}^2+{F_{n+1}}^2$が従うなど，これだけでも十分に意味のある性質と感じます。以降の議論で使いたいので述べました。
さらに簡単に分かることで次の性質があります。
正の整数$n$に対して，$\gcd\left(F_n,\ F_{n+1}\right)=1$
$\gcd\left(F_n,\ F_{n+1}\right)=d$とすると，漸化式より$F_{n-1}$も$d$の倍数である。つまり$\gcd\left(F_{n-1},\ F_{n}\right)\geq d$が成り立つ。これを繰り返していくと，$\gcd\left(F_1,\ F_2\right)\geq d$でなければならないから，$d=1$に限る。◆
定理１の証明
定理１の証明にあたって，整数の性質の「ユークリッドの互除法」をうまく使えないかなあと考えます。まず，次の補題を示しましょう。
$n$が$m$で割り切れるならば，$F_n$は$F_m$で割り切れる。
$n=m$のときは明らか。
$n=km$のときに補題が正しいとする。$n=(k+1)m$のとき，補題２より，$$ F_n=F_m\cdot F_{km+1}+F_{m-1}\cdot F_{km} $$である。今，$F_{km}$は$F_m$の倍数と仮定していたので，$F_n$は$F_m$の倍数である。◆
$n,\ m$は自然数とする。このとき，$$ \gcd\left(F_{n+m},\ F_m\right)=\gcd\left(F_{n},\ F_m\right) $$
雰囲気は，$\gcd(AB+R,\ A)=\gcd(R,\ A)$に似ています。
最大公約数の性質をうまく使いながら変形する。
$$
\begin{align}
\gcd(F_{n+m},\ F_m)&= \gcd(F_m\cdot F_{n+1}+F_{m-1}\cdot F_{n}-F_m,\ F_m) && \because\textbf{補題２}\\
&= \gcd\big(F_{m-1}\cdot F_n,\ F_m\big)&& \because \gcd(AB+R,\ A)=\gcd(R,\ A)\\
&=\gcd(F_n,\ F_m)\quad \text{◆}&&\because \gcd(F_m,\ F_{m-1})=1
\end{align}
$$
ここまでの準備を元に，次の命題を示します。定理１の核となる命題です。
$n$を$m$で割った余りを$r$とすると，$$ \gcd(F_{n},\ F_m)=\gcd(F_m,\ F_r\,) $$
やはり雰囲気は，$\gcd(AB+R,\ A)=\gcd(R,\ A)$に似ています。
$q=1$のとき，$n=m+r$である。補題５より，$$ \gcd\left(F_{m+r},\ F_m\right)=\gcd\left(F_{r},\ F_m\right) $$が成り立つから命題は正しい。
$q=k$のときに命題が正しいとする。$q=k+1$のとき，$$
\begin{align}
\gcd(F_{(k+1)m+r},\ F_m)&=\gcd(F_{km+r},\ F_m)&&\because \textbf{補題５}\\
&=\gcd\left(F_{r},\ F_m\right)&&\because \textbf{帰納法の仮定}
\end{align}
$$
よって$q=k+1$でも正しい。◆
この命題６は定理１の核であり，ここからユークリッドの互除法と同様の手続きによって，定理１が正しいことが分かります。
例えば，$n$を$m$で割った余りを$r_1$とすると，$$
\gcd(F_{n},\ F_m)=\gcd(F_m,\ F_{r_1}\,)
$$です。さらに$m$を$r_1$で割った余りを$r_2$とすると，$$
\gcd(F_m,\ F_{r_1}\,)=\gcd(F_{r_1},\ F_{r_2}\,)
$$となります。以下同様に続けていくことで，ある数$r_k$を$a=\gcd(n,m)$で割った余りが0になります。つまり，$$
\gcd(F_{n},\ F_m)=\gcd(F_{r_k},\ F_{a}\,)=F_a
$$
です。これは定理１の結果になります。
まとめ
本記事では定理１を示すために，道中フィボナッチ数列のいくつかの性質を見ていきました。余りや約数との親和性もあって美しいですね。
ここまで読んでいただきありがとうございました。
