数列における余りの周期性（特にフィボナッチ数列）

各項を $p$ で割った余りは $0,1,\dots,p-1$ の $p$ 通りで有限個。よって，各項を $p$ で割った余りを初項から十分並べると，同じ2連続のパターンが現れる。同じ2連続のパターンが現れると，漸化式より，その後に続く数字たちの余りも同じなのでループする。

数列の各項は整数となる。各項を $p$ で割った余りは $0,1,\dots,p-1$ の $p$ 通りである。よって，隣り合うペア $(a_n,a_{n+1})$ をそれぞれ $p$ で割った余りのパターンは，高々 $p^2$ 通りである。よって，数列の最初の $p^2+1$ ペアを見ると，鳩の巣原理より，パターンが同じペア $(a_{n_1},a_{n_1+1}),(a_{n_2},a_{n_2+1})$ が存在する。(ただし，$n_1< n_2$ )

よって，漸化式を使うと，$p$ で割った余りについて $$\begin{aligned} a_{n_1+2}&\equiv a_{n_2+2}\\ a_{n_1+3}&\equiv a_{n_2+3}\\ &\;\; \vdots \end{aligned}$$ がわかる。つまり，帰納的に，任意の非負整数 $N$ に対して，

$$a_{n_1+N}\equiv a_{n_2+N}$$

であることがわかる。言い換えると，$n_1$ 以上である任意の整数 $N'$ に対して，

$$a_{N'}\equiv a_{N'+n_2-n_1}$$

これは，数列の余りがループすること（そして，ループの周期が $n_2-n_1$ の約数であること）を表している。

普通の三項間漸化式と同様に，

$$x^2\equiv x+1\pmod{p}$$

という「特性合同式」を考える。以下 $\mathrm{mod}\:p$ という記載は省略する。実は，$p$ を $5$ で割った余りが $1$ または $4$ なら，この合同式を満たす $1$ 以上 $p-1$ 以下の整数が2つ存在する（→補足1）ので，それらを $\alpha,\beta$ とおく。

普通の三項間漸化式と同様に，一般項は

$$a_n\equiv C_1\alpha^n+C_2\beta^n$$

と書けそうである。実際，このようにすれば特性合同式より，$a_{n+2}\equiv a_{n+1}+a_{n}$ を満たすので，あとは初期条件を満たすように $C_1,C_2$ をうまく決めればよい。初期条件は，

$$\begin{aligned} C_1\alpha+C_2\beta &\equiv 1\\ C_1\alpha^2+C_2\beta^2 &\equiv 1 \end{aligned}$$

である。2つめの式に，特性合同式： $\alpha^2\equiv \alpha+1$ などを用いると，

$$C_1(\alpha+1)+C_2(\beta+1)\equiv 1$$

となる。これと1つめの式より，

$$C_1+C_2\equiv 0$$

この結果と1つめの式より，$C_1=(\alpha-\beta)^{-1},C_2=-(\alpha-\beta)^{-1}$ となる（→補足2）。

結局，$a_n\equiv (\alpha-\beta)^{-1}(\alpha^n-\beta^n)$ である。この一般項の式に，フェルマーの小定理を適用すると，

$$\begin{aligned} &a_{n+p-1}\\ &\equiv (\alpha-\beta)^{-1} (\alpha^{n+p-1}-\beta^{n+p-1})\\ &\equiv (\alpha-\beta)^{-1} (\alpha^n-\beta^n)\\ &\equiv a_n \end{aligned}$$

であることがわかる。つまり，周期は $p-1$ の約数である。

$13$ で割った余りについて，$a_1=a_2=1$ で $a_3$ 以降も計算していくと $a_{29}\equiv a_{30}\equiv 1$ で周期 $28$ のループ。

一方，$2024$ を $28$ で割った余りは $8$ であるので $a_{2024}\equiv a_{8}\equiv 8$ である。