斐波那契循环节

斐波那契数列的模意义下循环节

以 (f_0 = 0,f_1 = 1,f_n = f_{n-1}+f_{n-2}) 为例。其中 (a,b) 为给定的常数。(10^3) 组询问，每次给定模数 (p(< 10^9))，求 (f) 的最小循环节。（其实(f_0,f_1)，以及递推式不同，也可以用类似的方法）

模板题。博客

可以找出任意一个循环节，那么最小循环节应该是这个循环节的一个约数。枚举判断即可。

p为奇素数

众所周知，(f_n = frac{phi^n - hat{phi}^n}{sqrt 5})。根据不同的递推式，也可以用特征根法求通项得到类似的式子。

发现无论是 (phi)，还是 (hat{phi})，还是分母，都含有 (sqrt 5) 的项。如果 (5) 在模 (p) 意义下是二次剩余，那么 (sqrt 5,phi,hat{phi}) 的循环节都是 (p-1)，那么可得 (f) 的循环节为 (p-1)。

但是，有时候 (5) 并不是二次剩余，但是这就意味着 (5^{(p-1)/2}=-1)。然后有一个神奇的式子(phi^p=hat{phi},hatphi^p=phi)。证明如下:

[phi^p = (frac{1+sqrt5}{2})^p = frac{(1+sqrt5)^p}{2} = frac{1-sqrt5}{2}=hatphi ]

其中用到了 ((a+b)^p=a^p+b^p) 和 (a^p=a)。(hatphi^p=phi) 的证明也类似。然后观察特征方程，根据韦达定理发现 (phihatphi=-1)，那么就有 (phi^2 hatphi^2 = 1)。

[f_{2p+2} = frac{phi^{2p+2} - hatphi^{2p+2}}{sqrt5}= 0 = f_0\ f_{2p+3} = frac{phi-hatphi}{sqrt 5} = f_1 ]

这个对于其余的递推式来说也一样，只不过可能需要要求 ((phihatphi)^2=1) 或者某些更好的式子（如 (phihatphi=1)）

于是，当 (5) 不是二次剩余的时候，(f) 的循环节长度为 (2p+2)。

p^k

有一个神奇的结论：

[L(p^k) = L(p) p^{k-1} ]

其中 (L(a)) 表示模数为 (a) 的斐波那契循环节长度。证明：

假设 (L(p)=m,m'=mp^{k-1})

[frac{phi^m-hatphi^m}{sqrt 5} = f_m=f_0=0 pmod p\ phi^m=hatphi^m pmod p\ (phi^{m})^{p^{k-1}} = (hatphi^m)^{p^{k-1}} pmod {p^k}\ frac{(phi^{m})^{p^{k-1}}- (hatphi^m)^{p^{k-1}}}{sqrt 5}=0=f_{m'}=f_0 pmod {p^k} ]

还有个更强的：

[frac{phi^{m+1} - hatphi^{m+1}}{sqrt 5} = f_{m+1}=f_1 = frac{phi-hatphi}{sqrt5}=1 pmod p\ phi^{m+1}-hatphi^{m+1} - phi+hatphi=0 pmod p\ phi(phi^m-1)-hatphi(hatphi^m-1)=0 pmod p\ (phi - hatphi)(phi^m-1)=0 pmod p\ phi^m=hatphi^m =1 pmod p\ (phi^{m})^{p^{k-1}} = (hatphi^m)^{p^{k-1}}=1 pmod {p^k}\ f_{m'+1} =frac{(phi^{m})^{p^{k-1}}phi- (hatphi^m)^{p^{k-1}}hatphi}{sqrt 5}=1=f_1 pmod {p^k} ]

所以 (L(p^k) = m' = L(p)m^{k-1})

其中用到了定理：如果 (a = 1 pmod p)，那么 (a^{p^k}=1 pmod {p^{k+1}})。可以用归纳法证明（见开头博客）。

此外，我尚未尝试在其它递推式的数列中使用此方法证明，但是对于 (f_n=3f_{n-1}-f_{n-2}) 的小范围打表中可以验证 (L(p^k) = L(p)p^{k-1})。

pq，且p,q互质

中国剩余定理可知，(L(pq)=lcm(L(p),L(q)),(gcd(p,q)=1))。

至少反过来证明 (lcm(L(p),L(q))) 为模 (pq) 的循环节不难。因为 (f(km)=0 pmod p,k in Z;f(km')=0 pmod q,k in Z)，所以 (f(klcm(m,m'))=0 pmod {pq},k in Z)

---

于是，我们可以用类似求积性函数的方法来求模 p 意义下的循环节。最后枚举一下约数即可。

一些技巧和结论

我们自然可以通过欧拉判别准则((dfrac{a}{p})=a^{(p-1)/2}) 来判断奇素数是否是二次剩余，但是还有个 (O(1)) 的方法：二次互反律，即对于两个奇素数 (p,q)，有 ((dfrac{p}{q}) cdot (dfrac{q}{p}) = (-1)^{frac{p-1}2} cdot (-1)^{frac{q-1}2})。于是可以转化为判断 (p) 是否在模 (5) 的意义下是二次剩余，这个可以 (O(1)) 判断:(1,4) 是，(2,3) 不是。

总复杂度：(O(sigma_0(n)log n))，瓶颈在于判断约数是否为循环节，需要矩乘。

有结论：答案不超过 (6p)。当然，对于 (p < 1000)，可以直接 (p^2) 地判断。

似乎可以直接在 (p) 为奇素数那里枚举 (p-1) 或 (2p+2) 的约数，其余不用枚举约数，最终就可以得到最小循环节。并不会证明，也仅限于斐波那契数列。