看了11篇题解，发现大家对于模$p^k$的周期为$\pi(p)p^{k-1}$的证明都是用$\frac{1+\sqrt{5}}{2}$升幂定理来做。但是对于$2^k$的特殊情况来说，$5$有没有二次剩余其实问题不大，扩个域就好了，但是没有逆元硬用感觉不太行。

模$2^k$的周期为$3\times 2^{k-1}$，证明用数学归纳法。首先$k=1$成立。我们假设$m\leq k$时模$2^m$的周期都是$3\times 2^{m-1}$已成立。那么：

$F_{3\times 2^{k-1}}\mod 2^k=0,F_{3\times 2^{k-1}+1}\mod 2^k=1$

由经典结论$F_{3\times 2^k}=F_{3\times 2^{k-1}}F_{3\times 2^{k-1}-1}+F_{3\times 2^{k-1}+1}F_{3\times 2^{k-1}}=F_{3\times 2^{k-1}}(F_{3\times 2^{k-1}-1}+F_{3\times 2^{k-1}+1})$

第一个因数里有$k$个$2$，第二个因数考虑模$2$意义下时$0$，所以乘起来是$2^{k+1}$的倍数。$F_{3\times 2^{k}}\mod 2^{k+1}=0$

$F_{3\times 2^{k}+1}=F_{3\times 2^{k-1}}^2+F_{3\times 2^{k-1+1}}^2$

第一项模$2^{k+1}$显然为$0$。由归纳假设$F_{3\times 2^{k-1}+1}=s\cdot2^{k}+1$

那么$F_{3\times 2^{k-1}+1}^2=s^22^{2k}+s2^{k+1}+1$

即$F_{3\times 2^{k}+1} \mod 2^{k+1}=0$

即$3\times 2^k+1$是模$2^{k+1}$的周期。归纳假设成立。