Fibonacci数の整数の性質

同義語：フィボナッチ数の整除性divisibility of Fibonacci numbers

概要

前提知識: 整数の割り算と互除法, 数学的帰納法と整列性, 漸化式の行列表示

高校での出発点：Fibonacci 数を割ってみる

$0,1$ から始めて、前の 2 つの数を足して次の数を作ると
$$ 0,\ 1,\ 1,\ 2,\ 3,\ 5,\ 8,\ 13,\ 21,\ 34,\ 55,\ 89,\ 144,\ \ldots $$
という数の列ができる。これが Fibonacci 数である。ここでは $n$ 番目の数を $F_n$ と書き、$F_0=0$、$F_1=1$ から数える。まず $F_1$ から $F_{24}$ までを素因数分解して並べてみる。

$n$	$F_n$	素因数分解	$n$	$F_n$	素因数分解
$1$	$1$	—	$13$	$233$	$233$
$2$	$1$	—	$14$	$377$	$13\cdot29$
$3$	$2$	$2$	$15$	$610$	$2\cdot5\cdot61$
$4$	$3$	$3$	$16$	$987$	$3\cdot7\cdot47$
$5$	$5$	$5$	$17$	$1597$	$1597$
$6$	$8$	$2^3$	$18$	$2584$	$2^3\cdot17\cdot19$
$7$	$13$	$13$	$19$	$4181$	$37\cdot113$
$8$	$21$	$3\cdot7$	$20$	$6765$	$3\cdot5\cdot11\cdot41$
$9$	$34$	$2\cdot17$	$21$	$10946$	$2\cdot13\cdot421$
$10$	$55$	$5\cdot11$	$22$	$17711$	$89\cdot199$
$11$	$89$	$89$	$23$	$28657$	$28657$
$12$	$144$	$2^4\cdot3^2$	$24$	$46368$	$2^5\cdot3^2\cdot7\cdot23$

表を眺めると、割り切れ方に規則があるように見える。

小さな数で割り切れる $F_n$

$F_n$ が偶数（$2$ で割り切れる）になるのは、表の範囲では $n=3,6,9,12,15,18,21,24$ で、ちょうど $n$ が $3$ の倍数のときである。$3=F_3$ に注意する。
$F_n$ が $3$ で割り切れるのは $n=4,8,12,16,20,24$ で、$n$ が $4$ の倍数のときである。$3=F_4$ である。
$F_n$ が $5$ で割り切れるのは $n=5,10,15,20$ で、$n$ が $5$ の倍数のときである。$5=F_5$ である。
$F_n$ が $8=F_6$ で割り切れるのは $n=6,12,18,24$ である。たとえば $F_{18}=2584=8\cdot323$ である。

どの行でも「割り切れる $n$ は、最初に割り切れる $n$ の倍数全体」になっている。図 1 は、ほかの数 $d$ でも同じことが起こることを $n\le30$ で示したものである。
F_n が d で割り切れる n を大きな点で示した図。赤は最初に割り切れる n で、青の点はその倍数のところに等間隔に並ぶ
次に、2 つの Fibonacci 数の最大公約数を互除法で求めてみる（互除法は整数の割り算と互除法で扱った）。

互除法で $\gcd(F_{12},F_{18})$ と $\gcd(F_{15},F_{20})$ を求める

$F_{12}=144$、$F_{18}=2584$ に互除法を使う。
$$ 2584=17\cdot144+136,\qquad 144=1\cdot136+8,\qquad 136=17\cdot8 $$
なので $\gcd(F_{12},F_{18})=8$ である。$8=F_6$ で、$6=\gcd(12,18)$ である。
$F_{15}=610$、$F_{20}=6765$ に互除法を使う。
$$ 6765=11\cdot610+55,\qquad 610=11\cdot55+5,\qquad 55=11\cdot5 $$
なので $\gcd(F_{15},F_{20})=5$ である。$5=F_5$ で、$5=\gcd(15,20)$ である。

どちらの例でも、最大公約数がまた Fibonacci 数になり、その番号は番号どうしの最大公約数になっている。この記事で答える問いは次の 4 つである。

$\gcd(F_m,F_n)=F_{\gcd(m,n)}$ はいつも成り立つか。→ thm-fdv-main
$F_m$ が $F_n$ を割り切るのはどんなときか。→ cor-fdv-divides
$F_n$ が素数になりうるのは、どんな $n$ のときか。→ cor-fdv-prime

ex-fdv-start-small と図 1 で、割り切れる $n$ が等間隔に並ぶのはなぜか。→ cor-fdv-rank

高校の計算	この記事の言葉	大学の言葉
漸化式 $F_{n+2}=F_{n+1}+F_n$ を繰り返し使う	加法公式	行列の積 $M^{m+n}=M^mM^n$
互除法で最大公約数を求める	番号の互除法	強い可除列
割り切れる $n$ の表	最初の $n$ の倍数全体	$\mathbb{Z}$ の部分群は $r\mathbb{Z}$ の形

Fibonacci 数の定義

Fibonacci 数

$$ F_0=0,\qquad F_1=1,\qquad F_{n+2}=F_{n+1}+F_n\quad(n=0,1,2,\ldots) $$
で定まる数の列 $F_0,F_1,F_2,\ldots$ を Fibonacci 数 という。

$F_1=F_2=1$ から始める本も多い。$F_0=0$ を付け加えても、$F_2=F_1+F_0=1$ となって同じ列になる。$F_0=0$ があると、後で出てくる式が $n=0$ でもそのまま使える。

定義どおりに計算する

$F_2=1+0=1$、$F_3=1+1=2$、$F_4=2+1=3$、$F_5=3+2=5$、$F_6=5+3=8$ である。
$F_7=8+5=13$、$F_8=13+8=21$、$F_9=21+13=34$、$F_{10}=34+21=55$ である。

大小関係を 1 つ確かめておく。これは後で cor-fdv-divides と cor-fdv-prime に使う。

Fibonacci 数は $F_2$ から先で増え続ける

$n\ge1$ なら $F_n\ge1$ であり、
$$ 1=F_1=F_2< F_3< F_4< F_5<\cdots $$
が成り立つ。

段 1（$F_n\ge1$）。$n$ についての帰納法で示す。$F_1=1$、$F_2=1$ である。$n\ge1$ で $F_n\ge1$、$F_{n+1}\ge1$ なら、$F_{n+2}=F_{n+1}+F_n\ge2\ge1$ である。よって $n\ge1$ のすべてで $F_n\ge1$ である（2 つ前までを仮定する帰納法。数学的帰納法と整列性）。
段 2（増える）。$n\ge2$ とする。定義から $F_{n+1}=F_n+F_{n-1}$ で、$n-1\ge1$ なので段 1 により $F_{n-1}\ge1$ である。よって $F_{n+1}\ge F_n+1>F_n$ である。$\square$

加法公式 $F_{m+n}=F_mF_{n+1}+F_{m-1}F_n$

漸化式は「隣の 2 つから次を作る」式である。これを繰り返すと、離れた番号の Fibonacci 数どうしを結ぶ式が得られる。

加法公式

$m\ge1$、$n\ge0$ の整数について
$$ F_{m+n}=F_mF_{n+1}+F_{m-1}F_n $$
が成り立つ。

証明の前に、数で確かめる。

加法公式を数で確かめる

$m=2$ のときは $F_2=F_1=1$ なので、式は $F_{n+2}=F_{n+1}+F_n$ で、漸化式そのものである。
$m=5$、$n=7$ のとき、右辺は $F_5F_8+F_4F_7=5\cdot21+3\cdot13=105+39=144$ で、左辺 $F_{12}=144$ と一致する。
$m=n=6$ のとき、右辺は $F_6F_7+F_5F_6=8\cdot13+5\cdot8=104+40=144$ で、やはり $F_{12}=144$ である。

方針：$m$ を固定して、$n$ についての帰納法で示す。漸化式が 2 つ前までを使うので、$n$ と $n+1$ の場合から $n+2$ の場合を導く。
段 1（$n=0$）。右辺は $F_mF_1+F_{m-1}F_0=F_m\cdot1+F_{m-1}\cdot0=F_m$ で、左辺 $F_{m+0}=F_m$ と等しい。
段 2（$n=1$）。右辺は $F_mF_2+F_{m-1}F_1=F_m+F_{m-1}$ である。$m\ge1$ なので $m-1\ge0$ で、漸化式 $F_{(m-1)+2}=F_{(m-1)+1}+F_{m-1}$ により、これは $F_{m+1}$ に等しい。
段 3（$n$ と $n+1$ から $n+2$ へ）。$n$ と $n+1$ で式が成り立つと仮定する。漸化式と仮定により
$$ \begin{aligned} F_{m+n+2}&=F_{m+n+1}+F_{m+n}\\ &=\bigl(F_mF_{n+2}+F_{m-1}F_{n+1}\bigr)+\bigl(F_mF_{n+1}+F_{m-1}F_n\bigr)\\ &=F_m\underbrace{\bigl(F_{n+2}+F_{n+1}\bigr)}_{=F_{n+3}}+F_{m-1}\underbrace{\bigl(F_{n+1}+F_n\bigr)}_{=F_{n+2}}\\ &=F_mF_{n+3}+F_{m-1}F_{n+2} \end{aligned} $$
である。最後の式は $n+2$ の場合の右辺である。
段 1〜3 により、すべての $n\ge0$ で式が成り立つ。$\square$

行列の積を使う別証明を開く

$M=\begin{pmatrix}1&1\\1&0\end{pmatrix}$ とおくと、$n\ge1$ で $M^n=\begin{pmatrix}F_{n+1}&F_n\\ F_n&F_{n-1}\end{pmatrix}$ である（漸化式の行列表示）。実際、$n=1$ では右辺が $\begin{pmatrix}1&1\\1&0\end{pmatrix}=M$ であり、$M^n$ がこの形なら

$$M^{n+1}=M^nM=\begin{pmatrix}F_{n+1}+F_n&F_{n+1}\\ F_n+F_{n-1}&F_n\end{pmatrix}=\begin{pmatrix}F_{n+2}&F_{n+1}\\ F_{n+1}&F_n\end{pmatrix}$$

となる。$m,n\ge1$ のとき、$M^{m+n}=M^mM^n$ の左下の成分を比べる。左辺の左下は $F_{m+n}$ である。右辺の左下は、$M^m$ の下の行 $(F_m,\ F_{m-1})$ と $M^n$ の左の列 $(F_{n+1},\ F_n)$ の積の和で、$F_mF_{n+1}+F_{m-1}F_n$ である。$n=0$ の場合は上の証明の段 1 と同じである。

最大公約数についての 2 つの補題

主定理の証明には、最大公約数についての補題が 2 つ要る。どちらも整数の割り算と互除法の次の 2 つの事実から出る。

補題「割り算で公約数は変わらない」：整数 $a,b,q$ について $\gcd(a,b)=\gcd(b,a-qb)$。
定理「整数の Bézout の等式」：$\gcd(a,b)=1$ なら、$ax+by=1$ を満たす整数 $x,y$ がある。

隣り合う Fibonacci 数は互いに素

すべての $n\ge0$ について $\gcd(F_n,F_{n+1})=1$ である。

$n$ についての帰納法で示す。$n=0$ では $\gcd(F_0,F_1)=\gcd(0,1)=1$ である。
$\gcd(F_n,F_{n+1})=1$ と仮定する。$F_{n+2}-1\cdot F_{n+1}=F_n$ なので、「割り算で公約数は変わらない」を $a=F_{n+2}$、$b=F_{n+1}$、$q=1$ として使うと
$$ \gcd(F_{n+1},F_{n+2})=\gcd(F_{n+2},F_{n+1})=\gcd(F_{n+1},F_n)=1 $$
である。よってすべての $n\ge0$ で成り立つ。$\square$

隣り合う Fibonacci 数の最大公約数

$F_{11}=89$、$F_{12}=144$ に互除法を使うと $144=1\cdot89+55$、$89=1\cdot55+34$、…と、余りが $55,34,21,13,8,5,3,2,1$ と Fibonacci 数をさかのぼり、最後の $0$ でない余りは $1$ である。
表の素因数分解でも、$F_{18}=2^3\cdot17\cdot19$ と $F_{19}=37\cdot113$ は共通の素因数をもたない。

で余りが Fibonacci 数をさかのぼるのは、隣り合う Fibonacci 数の割り算では、最後の $2=2\cdot1$ を除いて商がいつも $1$ だからである。このため互除法の回数が最も多くなる（Lamé の定理。整数の割り算と互除法）。隣り合う Fibonacci 数に互除法を使ってみる演習は Cri24 の第 2 章にもある。

互いに素な数を掛けても最大公約数は変わらない

整数 $a,b,c$ について $\gcd(a,b)=1$ なら、$\gcd(a,bc)=\gcd(a,c)$ である。

$a$ と $c$ の公約数全体と、$a$ と $bc$ の公約数全体が一致することを示す。一致すれば、その中の最大のものも一致する。
段 1。$k$ が $a$ と $c$ の公約数なら、$k\mid c$ から $k\mid bc$ なので、$k$ は $a$ と $bc$ の公約数である。
段 2。$k$ が $a$ と $bc$ の公約数とする。$\gcd(a,b)=1$ なので、Bézout の等式により $ax+by=1$ を満たす整数 $x,y$ がある。両辺に $c$ を掛けると
$$ c=a\cdot(cx)+(bc)\cdot y $$
である。$k\mid a$、$k\mid bc$ なので、右辺の 2 つの項はどちらも $k$ の倍数で、$k\mid c$ である。よって $k$ は $a$ と $c$ の公約数である。$\square$

補題の条件を確かめる

$a=8$、$b=13$、$c=6$ では $\gcd(8,13)=1$ で、$\gcd(8,13\cdot6)=\gcd(8,78)=2=\gcd(8,6)$ である。
条件 $\gcd(a,b)=1$ を外すと崩れる。$a=4$、$b=2$、$c=2$ では $\gcd(4,2\cdot2)=4$ だが $\gcd(4,2)=2$ である。

主定理：$\gcd(F_m,F_n)=F_{\gcd(m,n)}$

鍵になるのは、番号の引き算が最大公約数を変えないことである。

番号を引いても最大公約数は変わらない

$1\le m< n$ のとき
$$ \gcd(F_m,F_n)=\gcd(F_m,F_{n-m}) $$
である。

段 1（加法公式）。$n-m\ge1$ なので、lem-fdv-add を $m$ と $n-m$ に使うと
$$ F_n=F_{m+(n-m)}=F_mF_{n-m+1}+F_{m-1}F_{n-m} $$
である。
段 2（$F_m$ の倍数を引く）。段 1 より $F_n-F_{n-m+1}\cdot F_m=F_{m-1}F_{n-m}$ である。「割り算で公約数は変わらない」を $a=F_n$、$b=F_m$、$q=F_{n-m+1}$ として使うと
$$ \gcd(F_m,F_n)=\gcd(F_m,\ F_{m-1}F_{n-m}) $$
である。
段 3（互いに素な因数を外す）。$m-1\ge0$ なので、lem-fdv-coprime により $\gcd(F_{m-1},F_m)=1$ である。lem-fdv-gcd-mult を $a=F_m$、$b=F_{m-1}$、$c=F_{n-m}$ として使うと
$$ \gcd(F_m,\ F_{m-1}F_{n-m})=\gcd(F_m,F_{n-m}) $$
である。段 2 と合わせて結論を得る。$\square$

$m=12$、$n=18$ で確かめる

段 1 の式は $F_{18}=F_{12}F_7+F_{11}F_6=144\cdot13+89\cdot8=1872+712=2584$ である。$F_{12}=144$ の倍数 $1872$ を引くと $712=89\cdot8$ が残る。$\gcd(144,89)=1$ なので $89$ を外してよく、
$$ \gcd(F_{12},F_{18})=\gcd(144,712)=\gcd(144,8)=8 $$
となる。ex-fdv-start-gcd の (1) と同じ答えである。

Fibonacci 数の最大公約数

正の整数 $m,n$ について
$$ \gcd(F_m,F_n)=F_{\gcd(m,n)} $$
が成り立つ。

方針：prop-fdv-step で番号の組 $(m,n)$ を $(m,n-m)$ に取り替えても、両辺が変わらないことを使う。番号の和 $m+n$ についての強い帰納法（数学的帰納法と整列性）で示す。
$m+n=s$ とし、和が $s$ より小さい正の整数の組ではすべて成り立つと仮定する。
段 1（$m=n$ のとき）。$F_m\ge1$（lem-fdv-increase）なので $\gcd(F_m,F_m)=F_m$ であり、$\gcd(m,m)=m$ なので右辺も $F_m$ である。
段 2（$m< n$ のとき）。prop-fdv-step により $\gcd(F_m,F_n)=\gcd(F_m,F_{n-m})$ である。組 $(m,n-m)$ はどちらも正の整数で、和は $m+(n-m)=n< s$ である。帰納法の仮定により $\gcd(F_m,F_{n-m})=F_{\gcd(m,n-m)}$ である。さらに「割り算で公約数は変わらない」を $a=n$、$b=m$、$q=1$ として使うと $\gcd(m,n-m)=\gcd(m,n)$ である。まとめると
$$ \gcd(F_m,F_n)=\gcd(F_m,F_{n-m})=F_{\gcd(m,n-m)}=F_{\gcd(m,n)} $$
である。
段 3（$m>n$ のとき）。$m$ と $n$ を入れかえると段 2 の場合になり、両辺とも入れかえで変わらないので成り立つ。
段 1〜3 により、和が $s$ の組でも成り立つ。$s=2$（$m=n=1$）は段 1 の場合なので、帰納法の出発点も確かめられている。$\square$

証明は、番号の組に「大きい方から小さい方を引く」互除法を行い、それと並行して Fibonacci 数の組にも互除法を行っている。$(m,n)=(12,18)$ で並べると次の図式になる。
$$ \xymatrix{ (12,18) \ar[r] \ar[d]_{F} & (12,6) \ar[r] \ar[d]_{F} & (6,6) \ar[d]_{F} \\ \gcd(F_{12},F_{18}) \ar@{=}[r] & \gcd(F_{12},F_6) \ar@{=}[r] & \gcd(F_6,F_6)=F_6 } $$
上の段の矢印は「大きい方から小さい方を引く」操作で、縦の矢印は番号を Fibonacci 数に取り替えることである。等式で書くと
$$ \gcd(F_{12},F_{18})=\gcd(F_{12},F_{6})=\gcd(F_6,F_6)=F_6=8 $$
であり、上の段の終わり $(6,6)$ の $6$ が $\gcd(12,18)$ である。

主定理を使って最大公約数を求める

$\gcd(F_{20},F_{30})=F_{\gcd(20,30)}=F_{10}=55$ である。素因数分解 $F_{20}=6765=3\cdot5\cdot11\cdot41$、$F_{30}=832040=2^3\cdot5\cdot11\cdot31\cdot61$ からも、共通部分は $5\cdot11=55$ である。
$\gcd(F_{19},F_{21})=F_{\gcd(19,21)}=F_1=1$ である。表の $F_{19}=37\cdot113$、$F_{21}=2\cdot13\cdot421$ は共通の素因数をもたない。

図 2 は $\gcd(m,n)$ の表、図 3 は $\gcd(F_m,F_n)$ の表で、同じ色のます目には、thm-fdv-main により $\gcd(m,n)=g$ と $\gcd(F_m,F_n)=F_g$ が入っている。

m, n = 1〜12 での gcd(m, n) の表。色は gcd(m, n) の大きさで塗った

m, n = 1〜12 での gcd(F_m, F_n) の表。色の塗り方は左の図と同じで、どのます目も左の数 g に対する F_g になっている

主定理から分かること

割り切れる関係

Fibonacci 数の割り切れる関係

$m,n$ を正の整数とする。
(1) $m\mid n$ なら $F_m\mid F_n$ である。
(2) $m\ge3$ で $F_m\mid F_n$ なら $m\mid n$ である。

$m\mid n$ なら $\gcd(m,n)=m$ なので、thm-fdv-main により $\gcd(F_m,F_n)=F_m$ である。最大公約数は $F_n$ を割り切るので、$F_m\mid F_n$ である。
$g=\gcd(m,n)$ とおく。$F_m\mid F_n$ で $F_m\ge1$ なので $\gcd(F_m,F_n)=F_m$ であり、thm-fdv-main により $F_g=F_m$ である。$g$ は $m$ の約数なので $1\le g\le m$ である。$g< m$ と仮定して矛盾を導く。

$g\ge2$ のとき、$2\le g< m$ なので lem-fdv-increase により $F_g< F_m$ である。
$g=1$ のとき、$F_g=F_1=1$ である。一方 $m\ge3$ なので lem-fdv-increase により $F_m\ge F_3=2$ である。よって $F_g< F_m$ である。
どちらでも $F_g=F_m$ に反する。よって $g=m$ で、$m=\gcd(m,n)$ は $n$ を割り切る。$\square$

割り切れる例と割り切れない例

$F_4=3$ は $F_8=21=3\cdot7$、$F_{12}=144=3\cdot48$、$F_{16}=987=3\cdot329$ を割り切る。$8,12,16$ は $4$ の倍数である。
$6$ は $9$ を割り切らないので、$F_6=8$ は $F_9=34$ を割り切らない。実際 $34=4\cdot8+2$ である。

$F_n$ が素数になる $n$

Fibonacci 数が素数になるための必要条件

$n\ge3$ で $F_n$ が素数なら、$n=4$ であるか、$n$ が素数である。

対偶を示す。$n\ge3$ で、$n\ne4$ かつ $n$ が素数でないとする。$F_n$ が素数でないことを示す。
段 1（$3$ 以上の約数を見つける）。$n$ は $3$ 以上で素数でないので、$n=ab$、$2\le a\le b< n$ と書ける。$a\ge3$ なら $c=a$ とする。$a=2$ なら $n=2b$ で、$n\ne4$ かつ $n\ge3$ から $n\ge6$、したがって $b\ge3$ なので $c=b$ とする。どちらでも $c$ は $n$ の約数で、$3\le c< n$ である。
段 2（$F_c$ が真の約数）。cor-fdv-divides の (1) により $F_c\mid F_n$ である。lem-fdv-increase により、$c\ge3$ から $F_c\ge F_3=2$、$2\le c< n$ から $F_c< F_n$ である。よって $F_n$ は $1$ でも自分自身でもない約数 $F_c$ をもち、素数でない。$\square$

$n=4$ が除かれないのは、$F_4=3$ が素数だからである。$4=2\cdot2$ の約数 $2$ に対する $F_2=1$ は、$F_4$ の真の約数にならない。

素数になる $F_n$

表の $n\le24$ で $F_n$ が素数になるのは $n=3,4,5,7,11,13,17,23$ で、$F_n=2,3,5,13,89,233,1597,28657$ である。$n=4$ 以外はすべて素数である。
$n=12$ は素数でない。cor-fdv-prime の証明の段 1 では $12=2\cdot6$ から $c=6$ をとり、$F_6=8$ が $F_{12}=144$ の真の約数になる。

逆は成り立たない。$n$ が素数でも $F_n$ が素数とは限らない（ex-fdv-cx-19）。

割り切れる番号が等間隔に並ぶ理由

$d$ で割り切れる番号は倍数全体

正の整数 $d$ について、$d\mid F_n$ となる正の整数 $n$ があるとし、そのうち最小のものを $r$ とする。このとき、正の整数 $n$ について
$$ d\mid F_n\iff r\mid n $$
である。

段 1（$\Leftarrow$）。$r\mid n$ なら、cor-fdv-divides の (1) により $F_r\mid F_n$ である。$d\mid F_r$ なので $d\mid F_n$ である。
段 2（$\Rightarrow$）。$d\mid F_n$ とする。$d$ は $F_r$ と $F_n$ の公約数なので、最大公約数 $\gcd(F_r,F_n)$ を割り切る（公約数は最大公約数を割り切る。整数の割り算と互除法の定理「整数の Bézout の等式」）。thm-fdv-main により $\gcd(F_r,F_n)=F_{\gcd(r,n)}$ なので、$d\mid F_{\gcd(r,n)}$ である。$\gcd(r,n)$ は $1$ 以上 $r$ 以下の整数で、$r$ は $d\mid F_n$ となる最小の正の $n$ だから、$\gcd(r,n)=r$ である。よって $r\mid n$ である。$\square$

最初に割り切れる番号

$d=4$：$F_1,\ldots,F_5=1,1,2,3,5$ は $4$ で割り切れず、$F_6=8$ が最初である。よって $4\mid F_n\iff6\mid n$ である。$2\mid F_3$ でも $4=2^2$ の $r$ は $3$ ではない。
$d=10$：最初は $F_{15}=610$ で、$10\mid F_n\iff15\mid n$ である。$2$ の $r=3$ と $5$ の $r=5$ の最小公倍数が $15$ になっている。
図 1 の $d=7$、$11$、$13$ では、$r=8$（$F_8=21$）、$r=10$（$F_{10}=55$）、$r=7$（$F_7=13$）である。

cor-fdv-rank は「$d\mid F_n$ となる $n$ がある」ことを仮定している。実はどの $d$ にもそのような $n$ がある。

どの正の整数 $d$ にも $d\mid F_n$ となる $n\ge1$ があることの証明を開く

$F_n$ を $d$ で割った余りを $R_n$ とし、組 $(R_n,R_{n+1})$ を考える。組の取りうる値は $d^2$ 通りしかないので、$n=0,1,\ldots,d^2$ の $d^2+1$ 個の組のうち、等しいものが 2 つある：$(R_i,R_{i+1})=(R_j,R_{j+1})$、$0\le i< j$。漸化式を $F_{n}=F_{n+2}-F_{n+1}$ と逆向きに使うと、$R_n$ は $(R_{n+1},R_{n+2})$ から決まる。よって $i\ge1$ なら $(R_{i-1},R_i)=(R_{j-1},R_j)$ で、これを繰り返すと $(R_0,R_1)=(R_{j-i},R_{j-i+1})$ となる。$R_0=0$ なので $R_{j-i}=0$、つまり $d\mid F_{j-i}$ で、$j-i\ge1$ である。この考え方で余りの列が周期的になることは、行列のn乗と割り算の余りでも扱う。

例と反例

外す条件	反例	成り立たなくなること
cor-fdv-prime の逆（$n$ が素数）	$n=19$	$F_n$ が素数
cor-fdv-divides の (2) の $m\ge3$	$m=2$、$n=3$	$F_m\mid F_n$ なら $m\mid n$
初期値 $F_0=0$、$F_1=1$	Lucas 数（$L_0=2$、$L_1=1$）	$\gcd(L_m,L_n)=L_{\gcd(m,n)}$、$m\mid n\Rightarrow L_m\mid L_n$

反例：$F_{19}$ は素数でない

$19$ は素数だが、$F_{19}=4181=37\cdot113$ は素数でない（$37\cdot113=3700+481=4181$）。cor-fdv-prime は「$F_n$ が素数なら $n$ は素数（または $4$）」という必要条件であり、十分条件ではない。

反例：$m=2$ では割り切れる関係の逆が崩れる

$F_2=1$ はすべての整数を割り切るので、$F_2\mid F_3=2$ である。しかし $2$ は $3$ を割り切らない。cor-fdv-divides の (2) の証明では、$g=1$ の場合に $F_1< F_m$ を使ったが、$m=2$ では $F_1=F_2=1$ なのでこれが使えない。

反例：初期値を変えた Lucas 数

同じ漸化式 $L_{n+2}=L_{n+1}+L_n$ で、初期値を $L_0=2$、$L_1=1$ に変えた列
$$ 2,\ 1,\ 3,\ 4,\ 7,\ 11,\ 18,\ 29,\ 47,\ 76,\ \ldots $$
を Lucas 数という。$\gcd(L_2,L_4)=\gcd(3,7)=1$ だが $L_{\gcd(2,4)}=L_2=3$ である。また $3\mid6$ だが $L_3=4$ は $L_6=18$ を割り切らない。lem-fdv-coprime の出発点 $\gcd(F_0,F_1)=\gcd(0,1)=1$ と、lem-fdv-add の段 1 の $F_0=0$ が、初期値 $0,1$ を使っていた。

演習

最大公約数を Fibonacci 数で表す

$\gcd(F_{24},F_{36})$ と $\gcd(F_{75},F_{100})$ を、それぞれ 1 つの Fibonacci 数 $F_k$ の形で表せ。前者は値も求めよ。

解答を開く

thm-fdv-main により $\gcd(F_{24},F_{36})=F_{\gcd(24,36)}=F_{12}=144$ である。$\gcd(75,100)=25$ なので $\gcd(F_{75},F_{100})=F_{25}$ である（$F_{25}=75025$）。

偶数になる Fibonacci 数

$F_n$（$n\ge1$）が偶数であるための必要十分条件は、$n$ が $3$ の倍数であることを示せ。

解答を開く

$F_1=1$、$F_2=1$ は奇数で、$F_3=2$ は偶数である。よって $d=2$ で $2\mid F_n$ となる最小の正の $n$ は $r=3$ である。cor-fdv-rank により、$2\mid F_n\iff3\mid n$ である。

大学数学で見る：強い可除列

正の整数の列 $a_1,a_2,a_3,\ldots$ が、すべての正の整数 $m,n$ で
$$ \gcd(a_m,a_n)=a_{\gcd(m,n)} $$
を満たすとき、強い可除列という。thm-fdv-main は「Fibonacci 数は強い可除列である」と言い換えられる。強い可除列では、cor-fdv-divides の (1)（$m\mid n\Rightarrow a_m\mid a_n$）が同じ証明で成り立つ。もう 1 つの代表例が $a_n=2^n-1$ で、完全数や Mersenne 素数の話（完全数とMersenne素数）で使われる。

$2^n-1$ が強い可除列であることの証明と、Fibonacci 数との共通点を開く

$1\le m< n$ とする。$2^n-1=2^{n-m}(2^m-1)+(2^{n-m}-1)$ なので、「割り算で公約数は変わらない」により

$$\gcd(2^m-1,\ 2^n-1)=\gcd(2^m-1,\ 2^{n-m}-1)$$

である。これは prop-fdv-step と同じ形の式で、thm-fdv-main の証明と同じく番号の和についての帰納法で $\gcd(2^m-1,2^n-1)=2^{\gcd(m,n)}-1$ が得られる。たとえば $\gcd(2^{12}-1,2^{18}-1)=\gcd(4095,262143)=63=2^6-1$ である。cor-fdv-prime と同じ議論で、$n\ge2$ で $2^n-1$ が素数なら $n$ は素数である。こちらは $a_2=2^2-1=3$ が $1$ より大きいので、$n=4$ のような例外はない（$2^4-1=15$ は $2^2-1=3$ で割り切れる）。

2 つの列はどちらも、$U_0=0$、$U_1=1$、$U_{n+2}=PU_{n+1}-QU_n$ の形の漸化式で作られる。Fibonacci 数は $P=1$、$Q=-1$、$2^n-1$ は $P=3$、$Q=2$ の場合である（$0,1,3,7,15,31,\ldots$）。一般の $P,Q$ でいつ強い可除列になるかは、この記事では扱わない。

また、cor-fdv-rank により、$d\mid F_n$ となる正の番号 $n$ の全体は、ある $r$ の正の倍数全体になる。大学の代数では、足し算と引き算で閉じた $\mathbb{Z}$ の部分集合（部分群）は必ずある数の倍数全体 $r\mathbb{Z}$ になることを学ぶ。cor-fdv-rank の証明で最大公約数 $\gcd(r,n)$ を使ったのは、この事実の証明で最小の正の元を使うのと同じ考え方である。

さらに先へ

隣り合う Fibonacci 数で互除法の回数が最も多くなることは、Lamé の定理として整数の割り算と互除法で扱う。Cassini の恒等式 $F_{n+1}F_{n-1}-F_n^2=(-1)^n$ は行列のn乗と割り算の余り、一般項（Binet の公式）は漸化式の行列表示と Fibonacci数の母関数にある。
隣り合う Fibonacci 数の比 $\dfrac{F_{n+1}}{F_n}$ は、黄金比の連分数 $1+\cfrac1{1+\cfrac1{1+\cdots}}$ を途中で打ち切った分数である。互除法の商を並べる連分数は連分数（高校数学）で扱う。
thm-fdv-main の式と、$n\ge3$ で「$F_n\mid F_m$ と $n\mid m$ が同値」であることは、Wei26 にも載っている。