Fibonacci-iccanobiF - 遊び tokidoki 仕事

久々のエントリーとなるが，瓢箪からコマというか，思いつきである講義（というか，ほとんど自分が教えることなくfacilitatorのような役割をしている）で紹介した現象について．

世間的にはおそらくよく知られた話なのだろうが，Fibonacci数列をmodulo Fibonacci数で見ると周期的になるという事実．
話を揃えよう．数列 $\{F_n\}$ を

$\displaystyle F_1=F_2=1,F_{n+2}=F_{n+1}+F_n$

で定義する．
で，これを $\pmod{F_n}, n\ge 4$ で観察すると

$\displaystyle n\text{ が奇数なら } 4n, n\text{ が偶数なら }2n$

の周期をもつ数列に変わる．
例えば $\pmod{F_4}=\pmod{3}$ なら

$\displaystyle 1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,\dots\\ \equiv 1,1,2,0,2,2,1,0,1,1,2,0,2,2,1,0,\dots\\$

で，周期は $4\times2=8$ ， $\pmod{F_5}=\pmod{5}$ なら

$\displaystyle 1,1,2,3,0,3,3,1,4,0,4,4,3,2,0,2,2,4,1,0,1,1,2,\dots\\$

で，周期は $5\times4=20$ ， $\pmod{F_6}=\pmod{8}$ なら

$\displaystyle 1,1,2,3,5,0,5,5,2,7,1,0,1,1,\dots\\$

で，周期は $8\times2=12$ ， $\pmod{F_7}=\pmod{13}$ なら

$\displaystyle 1,1,2,3,5,8,0,8,8,3,11,1,12,0,12,12,11,10,8,5,0,5,5,10,2,12,1,0,1,1,\dots\\$

で，周期は $7\times4=28$ といった具合だ．
これをもう少し続けたのが下の図．きれいに周期が出ている．
（因みに，学生はこれを見て「ファミマ」とか言っていた．）
f:id:okiraku894:20210725195825p:plain

さて，何が起こっているのだろう．紹介はしたものの，直感的に理解できていない．
学生らには，自由に研究活動をしてもらって何かを見つけてもらいたいが，自分は自分でこの現象の仕組みを理解したい．

数日折りに触れ考えていたところ，ようやくハッキリした．
例えば $\pmod{F_7}=\pmod{13}$ の列

$\displaystyle 1,1,2,3,5,8,0,8,8,3,11,1,12,0,\\\qquad 12,12,11,10,8,5,0,5,5,10,2,12,1,0\\$

は $F_k\equiv F_k-13\pmod{13}$ を通して一つおきに書き換えると，

$\displaystyle 1,-12,2,-10,5,-5,0,-5,8,-10,11,-12,12,0,\\\qquad 12,-1,11,-3,8,-8,0,-8,5,-3,2,-1,1,0\\$

といった列になるが，これは元の周期列を一つおきに負号を付けて逆に並べたものになる．
これはもともとの漸化式

$\displaystyle F_{n+2}=F_{n+1}+F_n$

を

$\displaystyle F_{n}=F_{n+2}-F_{n+1}$

と書き直して理解できそうだ．
また $\pmod{F_n}$ では $F_{n-2}+F_{n-1}=F_{n}\equiv 0$ ，つまり $F_{n-2}\equiv -F_{n-1}$ と理解できるから，

$\begin{align} &F_{n-3}=F_{n-1}-F_{n-2}\equiv 2F_{n-1}\\ &F_{n-4}=F_{n-2}-F_{n-3}\equiv -3F_{n-1}\\ &F_{n-5}=F_{n-3}-F_{n-4}\equiv 5F_{n-1}\\ &F_{n-6}=F_{n-4}-F_{n-5}\equiv -8F_{n-1}\\ &\vdots\\ &F_{n-k}=F_{n-k+2}-F_{n-k+1}\equiv (-1)^{k-1}F_kF_{n-1}\\ \end{align}$

と遡っていくと，特に $k=n-1$ では

$1=F_1\equiv (-1)^{n}F_{n-1}^2$

となるので，

$F_{n-1}^2\equiv (-1)^n\pmod{F_n}$

となる．特に $n$ が偶数なら $F_{n-1}^2\equiv1\pmod{F_n}$ だが， $F_{n-1}$ と $F_n$ は互いに素で $F_{n-1} < F_n$ だから

$F_{n-1}\equiv -1\pmod{F_n}$

となり，また

$F_{n+1}=F_{n}+F_{n-1}\equiv F_{n-1}\pmod{F_n}$
$F_{n+2}=F_{n+1}+F_{n}\equiv F_{n-1}\pmod{F_n}$

を考えると， $k\ge 1$ について帰納的に

$F_{n+k+2}=F_{n+k+1}+F_{n+k}\equiv F_{n-1}(F_{k+1}+F_{k})=F_{n-1}F_{k+2}\pmod{F_n}$

が分かり，特に $k=n-3,n-2,n-1$ で

$\begin{align} F_{2n-1}&\equiv F_{n-1}^2\equiv 1,\\ F_{2n}&\equiv F_{n-1}F_n\equiv0,\\ F_{2n+1}&\equiv F_{2n-1}+F_{2n}\equiv 1\pmod{F_n} \end{align}$

となるから，次の周期が始まる．すなわち， $\pmod{F_n}$ での周期は $2n$ と分かる．
一方， $n$ が奇数なら $F_{n-1}^2\equiv-1\pmod{F_n}$ であり，したがって $F_{n-1}^4\equiv1\pmod{F_n}$ となるから，偶数の場合と同様な議論によって， $\pmod{F_n}$ での周期は $4n$ と分かる．