斐波那契周期性
定义
\[Fib_1=1,Fib_2=1,Fib_n=Fib_{n-2}+Fib_{n-1} \]有通项公式：
\[Fib_n=\frac{1}{\sqrt 5}\left(\left(\frac{1+\sqrt 5}{2}\right)^n-\left(\frac{1-\sqrt 5}{2}\right)^n\right) \]周期的计算
引理1
对于奇素数 \(p\equiv 1\pmod 5\) 或 \(p\equiv 4\pmod 5\)，\(p-1\) 是一个周期。
证法一
此证法来自《数论概论》。
因为 \(p\equiv 1\pmod 5\) 或 \(p\equiv 4\pmod 5\)，故 \(p\) 是个 \(\text{QR}\)。
根据二次互反律，有：
\[\left(\frac{5}{p}\right)=\left(\frac{p}{5}\right)=\left(\frac{p\bmod 5}{5}\right)=\left(\frac{1}{5}\right)\text{或}\left(\frac{4}{p}\right)=1 \]故 \(5\) 为模 \(p\) 的二次剩余，于是存在整数 \(c^2\equiv 5\pmod p\)。由于 \(p\nmid c\) 且 \(p\) 是质数，\(c\) 存在逆元 \(c^{-1}\)。
我们定义模 \(p\) 意义下的序列 \(J\)：
\[J_n\equiv c^{-1}\Bigg(\left(\frac{1+c}{2}\right)^n-\left(\frac{1-c}{2}\right)^n\Bigg) \]由 \(c^2\equiv 5\pmod p\) 可知：
\[J_1\equiv J_2\equiv 1\pmod p,J_n\equiv J_{n-2}+J_{n-1}\pmod p \]于是 \(J\) 和 \(Fib\) 有相同的初值和递归关系，故有：
\[J_n\equiv Fib_n\pmod p \]我们记 \(U=\dfrac{p+1}{2},V=\dfrac{p-1}{2}\)
有：
\[Fib_n\equiv c^{-1}\left(U^n-V^n\right)\pmod p \]由费马小定理可知：
\[\begin{aligned} Fib_{i+(p-1)j}&\equiv c^{-1}\left(U^{i+(p-1)j}-V^{i+(p-1)j}\right)\pmod p\\ &\equiv c^{-1}\left(U^i-V^i\right)\pmod p\\ &\equiv Fib_i \end{aligned}\]即模 \(p\) 每 \(p-1\) 循环一个，即 \(p-1\) 是周期。
证法二
该证法来自 OIwiki。
由 \(C_n^m\) 计算式知：当 \(0<i<p\) 时，\(C_p^i\equiv 0\pmod p\)。
我们直接把 \(Fib_n\) 按照定义展开：
\[\begin{aligned} Fib_p&=\frac{\sum\limits_{i=0}^{p}C_p^i\sqrt 5^i-\sum\limits_{i=0}^{p}C_p^i(-\sqrt 5)^i}{2^p\sqrt5}\\ &\equiv \frac{C_p^0\sqrt5^0+C_p^p\sqrt5^p-(C_p^0(-\sqrt5)^0+C_p^p(-\sqrt5)^p)}{2^p\sqrt5}\pmod p\\ &\equiv \frac{\sqrt5^p+\sqrt5^p}{2^p\sqrt5}\pmod p\\ &\equiv \frac{\sqrt5^{p-1}}{2^{p-1}}\pmod p \end{aligned}\]由费马小定理，有 \(2^{p-1}\equiv 1\pmod p\)；\(5\) 为模 \(p\) 意义下的二次剩余，根据欧拉准则，有 \(5^{\tfrac{p-1}{2}}\equiv 1\pmod p\)，故：
\[Fib_p\equiv \sqrt5^p-1\equiv 5^{\tfrac{p-1}{2}}\equiv 1\pmod p \]用相似的方法展开 \(Fib_{p+1}\)，发现 \(Fib_{p+1}\equiv 1\pmod p\)。
故 \(Fib_{p}\) 和 \(Fib_{p+1}\) 两项都同余 \(1\)，与 \(Fib_1\) 和 \(Fib_2\) 一致，故 \(p-1\) 是周期。
引理2
对于奇素数 \(p\equiv 2\pmod 5\) 或 \(p\equiv 3\pmod 5\)，\(2p+2\) 是一个周期。
证明：
该证法来自 OIwiki。
相似的，我们直接展开 \(Fib_{2p}\) 和 \(Fib_{2p+1}\)：
\[\begin{aligned} Fib_{2p}&=\frac{2}{2^{2p}\sqrt 5}\left(C_{2p}^1\sqrt 5+C_{2p}^3\sqrt 5^3+\dots C_{2p}^{2p-1}\sqrt 5^{2p-1}\right)\\ &\equiv \frac{1}{2^{2p-1}\sqrt 5}C_{2p}^{p}\sqrt5^p\pmod p \end{aligned}\]可以验证，\(Fib_{2p}\) 的式子模了 \(p\) 之后只有 \(C_{2p}^{p}\) 项留了下来，又：
\[C_{2p}^p=\sum_{i=0}^{p}(C_p^i)^2 \]故：
\[C_{2p}^p\equiv (C_p^0)^2+(C_p^p)^2\equiv 2\pmod p \]所以根据费马小定理，有 \(2^{2p-2}\equiv 1\pmod p\)；而 \(5\) 又是模 \(p\) 下的二次非剩余，根据欧拉准则，有 \(5^{\tfrac{p-1}{2}}\equiv -1\pmod p\)，故：
\[Fib_{2p}\equiv \frac{\sqrt5^{p-1}}{2^{2p-2}}\equiv \sqrt5^{p-1}\equiv 5^{\tfrac{p-1}{2}}\equiv -1\pmod p \]用相似的方法展开 \(Fib_{2p+1}\)，套一些组合数的性质，发现 \(Fib_{2p+1}\equiv 1\pmod p\)。
而我们根据 \(Fib_{n}=Fib_{n-2}+Fib_{n-1}\)，可以倒着推出来 \(Fib_{-2}=-1,Fib_{-1}=1\)。
故 \(Fib_{p}\) 和 \(Fib_{p+1}\) 两项，与 \(Fib_{-2}\) 和 \(Fib_{-1}\) 一致，故 \(2p+2\) 是周期。
引理3
来自于这篇博客。
若 \(a\equiv 1\pmod p\)，则 \(a^{p^k}\equiv1\pmod {p^{k+1}}\)
证明：
归纳证明法。假设对于 \(k-1\) 成立，即：
\[a^{p^{k-1}}\equiv 1\pmod {p^k} \]我们设：
\[a^{p^{k-1}}=tp^k+1 \]则：
\[a^{p^k}=(a^{p^{k-1}})^p=(tp^k+1)^p= \sum_{i=0}^{p}(tp^k)^i \]在模 \(p^{k+1}\) 意义下，\(i\ge1\) 的项都没了，于是：
\[a^{p^k}\equiv (tp^k)^0\equiv 1\pmod {p^{k+1}} \]证毕。
引理4
来自于这篇博客。
若 \(p\) 为奇素数，\(p\) 的循环节为 \(t\)，那么有 $ tp^{k-1}$ 是\(p^k\) 的循环节。
证明：
我们记 \(U=\dfrac{1+\sqrt 5}{2},V=\dfrac{1-\sqrt 5}{2}\)
根据 \(t\) 为 \(p\) 的循环节，我们有：
\[0\equiv Fib_t \equiv \frac{1}{\sqrt 5}\Big(U^t-V^t\Big) \equiv U^t-V^t\pmod p \]故：
\[U^t\equiv V^t\pmod p \]又：
\[\begin{aligned} 1&\equiv Fib_{t+1}\equiv \frac{1}{\sqrt 5}\Big(U^{t+1}-V^{t+1}\Big) \equiv \frac{1}{\sqrt 5}\Big(U^t\cdot U-V^t\cdot V\Big)\\ &\equiv \frac{1}{\sqrt 5}\Big(U^t\cdot U-U^t\cdot V\Big)\equiv U^t\frac{1}{\sqrt 5}(U-V)\equiv U^tFib_1 \end{aligned}\]因为 \(Fib_1\equiv 1\pmod p\)，故 \(U^t\equiv V^t\equiv 1\pmod p\)
根据引理3，有：
\[U^{tp^{k-1}}\equiv V^{tp^{k-1}}\equiv 1\pmod {p^{k}} \]这蕴含着：
\[Fib_{tp^{k-1}}\equiv \frac{1}{\sqrt 5}(U^{tp^{k-1}}-V^{tp^{k-1}})\equiv 0\pmod {p^k} \]\[\begin{aligned} Fib_{tp^{k-1}+1}&\equiv \frac{1}{\sqrt 5}(U^{tp^{k-1}+1}-V^{tp^{k-1}+1})\equiv \frac{1}{\sqrt 5}(U^{tp^{k-1}}\cdot U-V^{tp^{k-1}}\cdot V)\\ &\equiv \frac{1}{\sqrt 5}(U^{tp^{k-1}}\cdot U-U^{tp^{k-1}}\cdot V)\equiv U^{tp^{k-1}} \frac{1}{\sqrt5}(U-V)\\ &\equiv U^{tp^{k-1}}Fib_1\equiv 1\pmod {p^k} \end{aligned}\]即 \(tp^{k-1}\) 是模 \(p^k\) 的循环节。
综合上述四个引理，我们就找到了一种计算斐波那契在模 \(m\) 意义下的循环节（注意，不是最小的）的方法：
-
对 \(m\) 分解质因数：\(m=\prod\limits_{i=1}^{w}p_i^{c_i}\)
-
枚举 \(m\) 的每个质因子 \(p_i\)，根据引理1和2，计算模 \(p_i\) 意义下的循环节 \(t_i\)。（特别的，若 \(p_i=2\)，则循环节为 \(3\)；若 \(p_i=5\)，则循环节为 \(20\)）
-
根据引理3，计算出模 \(p_i^{c_i}\) 意义下的循环节 \(T_i=t_ip_i^{c_i-1}\)。
-
最后，计算模 \(m\) 意义下的循环节 \(T=\operatorname{lcm}_{i=1}^{w}T_i\) 即可。