4

フィボナッチ数列で互除法っぽいこと

852
0
$$\newcommand{beku}[1]{\vec{#1\vphantom{b}}} \newcommand{bekutoru}[1]{\displaystyle\overrightarrow{\mbox{#1}\vphantom{b}}} \newcommand{bunsuu}[2]{\dfrac{\,#1\,}{\,#2\,}} \newcommand{dsqrt}[1]{\displaystyle\sqrt{\,#1\,}} \newcommand{gauss}[1]{\left[\mkern1mu {#1}\mkern1mu\right]} \newcommand{kaku}[1]{\angle\mbox{#1}} \newcommand{kumiawase}[2]{\mathord{{}_{#1}\kern-.12em{}\text{C}_{#2}}} \newcommand{sankaku}[1]{\triangle \mbox{#1}} \newcommand{suuretu}[1]{\left\{#1\right\}} \newcommand{tsqrt}[1]{\textstyle\sqrt{\,#1\,}} \newcommand{zyunretu}[2]{\mathord{{}_{#1}\kern-.12em{}\text{P}_{#2}}} $$

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 $$が成り立つ。

証明に向けて

やはりいくつか性質を見ていきながら,定理1が正しいことを見ていきます。ここではいくつか準備をします。

フィボナッチ数の加法定理

$m,\ n$$1< m< n$を満たす自然数とする。このとき次が成り立つ。$$ F_n=F_m\cdot F_{n-m+1}+F_{m-1}\cdot F_{n-m} $$

$\pmb{n}$を固定して$\pmb{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$に限る。◆

定理1の証明

定理1の証明にあたって,整数の性質の「ユークリッドの互除法」をうまく使えないかなあと考えます。まず,次の補題を示しましょう。

$n$$m$で割り切れるならば,$F_n$$F_m$で割り切れる。

$n=km$と表して,$\boldsymbol{k}$に関する帰納法

$n=m$のときは明らか。

$n=km$のときに補題が正しいとする。$n=(k+1)m$のとき,補題2より,$$ 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{補題2}\\ &= \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} $$

ここまでの準備を元に,次の命題を示します。定理1の核となる命題です。

ユークリッドの互除法っぽい?

$n$$m$で割った余りを$r$とすると,$$ \gcd(F_{n},\ F_m)=\gcd(F_m,\ F_r\,) $$

やはり雰囲気は,$\gcd(AB+R,\ A)=\gcd(R,\ A)$に似ています。

$\,n=qm+r\,$として,$q\,$に関する帰納法

$q=1$のとき,$n=m+r$である。補題5より,$$ \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{補題5}\\ &=\gcd\left(F_{r},\ F_m\right)&&\because \textbf{帰納法の仮定} \end{align} $$
よって$q=k+1$でも正しい。◆

この命題6は定理1の核であり,ここからユークリッドの互除法と同様の手続きによって,定理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 $$
です。これは定理1の結果になります。

まとめ

本記事では定理1を示すために,道中フィボナッチ数列のいくつかの性質を見ていきました。余りや約数との親和性もあって美しいですね。

ここまで読んでいただきありがとうございました。

投稿日:2020118

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

投稿者

ぱるち
ぱるち
125
17422
数学屋さんをしています。代数,数論系に興味があり,今は楕円曲線と戯れています。Mathlogは現実逃避用という噂もあります。@f_d00123

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中