广义斐波那契循环节

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial

广义斐波那契数递推公式 $$f_i=a{f}_{i-1}+b{f}_{i-2}(\mathrm{mod}p)(p\mathrm{是}\mathrm{奇}\mathrm{素}\mathrm{数})$$

他的转移矩阵 $$ ^n

p=

$$

如果存在循环节则存在n使得 $${\left[\begin{array}{cc}a& b\\ 1& 0\end{array}\right]}^n=\left[\begin{array}{cc}{k}_{1}p+1& k_{2}p+0\\ k_{3}p+0& k_{4}p+1\end{array}\right]$$

我们尝试把左边变成相似对角矩阵 先求特征值 $$(\lambda -a)\lambda -b=0\iff \lambda =\frac{a\pm \sqrt{a^2+4b}}{2}$$

当且仅当$a^2+4b=0$的时候，${\lambda }_1={\lambda }_2$，易证尽管此时$\lambda$是二重特征值，但是它对应的特征向量只有一个，即上诉矩阵不可对角化，我们不考虑这种复杂的情况。 当$a^2+4b\ne 0$的时候，两个特征向量分别为 $$\left[\begin{array}{c}{\lambda }_1\\ 1\end{array}\right]\mathrm{和}\left[\begin{array}{c}{\lambda }_2\\ 1\end{array}\right]$$ 那么就有了 $$\left[\begin{array}{cc}a& b\\ 1& 0\end{array}\right]=\left[\begin{array}{cc}{\lambda }_1& {\lambda }_2\\ 1& 1\end{array}\right]\left[\begin{array}{cc}{\lambda }_1& 0\\ 0& {\lambda }_2\end{array}\right]\left[\begin{array}{cc}\frac{1}{{\lambda }_1-{\lambda }_2}& \frac{-{\lambda }_2}{{\lambda }_1-{\lambda }_2}\\ \frac{-1}{{\lambda }_1-{\lambda }_2}& \frac{{\lambda }_1}{{\lambda }_1-{\lambda }_2}\end{array}\right]$$ 进而有了 $$\left[\begin{array}{cc}{\lambda }_1& {\lambda }_2\\ 1& 1\end{array}\right]\left[\begin{array}{cc}{\lambda }_1^n& 0\\ 0& {\lambda }_2^n\end{array}\right]\left[\begin{array}{cc}\frac{1}{{\lambda }_1-{\lambda }_2}& \frac{-{\lambda }_2}{{\lambda }_1-{\lambda }_2}\\ \frac{-1}{{\lambda }_1-{\lambda }_2}& \frac{{\lambda }_1}{{\lambda }_1-{\lambda }_2}\end{array}\right]=\left[\begin{array}{cc}{k}_{1}p+1& k_{2}p+0\\ k_{3}p+0& k_{4}p+1\end{array}\right]$$ 右乘$T$消掉那个一堆分数的矩阵 $$\left[\begin{array}{cc}{\lambda }_1& {\lambda }_2\\ 1& 1\end{array}\right]\left[\begin{array}{cc}{\lambda }_1^n& 0\\ 0& {\lambda }_2^n\end{array}\right]=\left[\begin{array}{cc}{k}_{1}p+1& k_{2}p+0\\ k_{3}p+0& k_{4}p+1\end{array}\right]\left[\begin{array}{cc}{\lambda }_1& {\lambda }_2\\ 1& 1\end{array}\right]$$ 乘开 $$\left[\begin{array}{cc}{\lambda }_1^{n+1}& {\lambda }_2^{n+1}\\ {\lambda }_1^n& {\lambda }_1^n\end{array}\right]=\left[\begin{array}{cc}{\lambda }_1(k_{1}p+1)+k_{2}p& {\lambda }_2(k_{1}p+1)+k_{2}p\\ {\lambda }_1{k}_{3}p+k_{4}p+1& {\lambda }_2{k}_{3}p+k_{4}p+1\end{array}\right]$$ ###在这之后我们分两部分讨论 ####$a^2+4b\mathrm{是}\mathrm{二}\mathrm{次}\mathrm{剩}\mathrm{余}$ 如果$a^2+4b$是二次剩余，那么${\lambda }_1$和${\lambda }_2$可以直接写成模意义下对应的整数,则上诉矩阵等式在$n=p-1$的时候根据费马小定理恒成立 ####$a^2+4b\mathrm{不}\mathrm{是}\mathrm{二}\mathrm{次}\mathrm{剩}\mathrm{余}$ 在这里，是绝对不能够直接取模的，因为$\lambda$中一旦包含了根号下非二次剩余，这里就是错的，我们不可以取模，直接用根式表达即可。 #####两矩阵相等条件1: $${\lambda }^n=\lambda k_{3}p+k_{4}p+1$$ 先看${\lambda }_1$ $${\lambda }_1=\frac{a+\sqrt{a^2+4b}}{2}=\frac{a}{2}+\frac{1}{2}\sqrt{a^2+4b}$$ 则 $$(\frac{a}{2}+\frac{1}{2}\sqrt{a^2+4b}{)}^n=(\frac{a}{2}+\frac{1}{2}\sqrt{a^2+4b})k_{3}p+k_{4}p+1$$ 分母有点难受，把它移到右边去 $$\begin{gathered} (a+\sqrt{a^2+4b}{)}^n=2^n\ast ((\frac{a}{2}+\frac{1}{2}\sqrt{a^2+4b})k_{3}p+k_{4}p+1) \\ \sum _{i=0}^n{C}_n^i{a}^i{\sqrt{a^2+4b}}^{n-i}=2^n\ast (\frac{a}{2}{k}_{3}p+k_{4}p+1)+2^n\ast (\frac{1}{2}{k}_{3}p)\sqrt{a^2+4b} \end{gathered}$$ 我们在这里引入一些概念，我们在实数领域解决这个问题，在实数领域，我们把数分为两部分来表示，一部分是有理数部分，称之为有理部，另一部分是无理数部分，称之为无理部，即$1+2\sqrt{16}$中，我们称1为有理部，2位无理部。 上式左边显然能够唯一表示为$x+y\sqrt{a^2+4b}$,那么两式相等的充要条件就是 $$\mathrm{存}\mathrm{在}{k}_3,k_4\mathrm{使}\mathrm{得}x=2^n\ast (\frac{a}{2}{k}_{3}p+k_{4}p+1),y=2^n\ast \frac{1}{2}{k}_{3}p$$ 上面的式子的某个充分条件为 $$\begin{gathered} \frac{x}{2^n}\equiv 1\mathrm{mod}p \\ \frac{y}{2^n}\equiv 0\mathrm{mod}p \end{gathered}$$ 更加具体一点如果n是(p-1)的倍数则下面的式子也是充分条件 $$\begin{gathered} x\equiv 1\mathrm{mod}p \\ y\equiv 0\mathrm{mod}p \end{gathered}$$ 为了利用这点，我们保证后面n一定是p-1的倍数，让我们先遗忘掉这些充分条件

然后我们来看看这个规律，注意到$\sum _{i=0}^n{C}_n^i{a}^i{\sqrt{a^2+4b}}^{n-i}$中，当$n=p\mathrm{且}i\ne 0\mathrm{且}i\ne n$的时候，$C_n^i|p$，所以 $$\begin{gathered} x\equiv a^p\equiv a \\ y\equiv {\sqrt{a^2+4b}}^p \end{gathered}$$ 即 $$\begin{array}{rl}& (a+\sqrt{a^2+4b}{)}^p\\ =& （a+c_{1}p)+({\sqrt{a^2+4b}}^{p-1}+c_{2}p)\sqrt{a^2+4b},c_1{c}_2\mathrm{是}\mathrm{整}\mathrm{数}\\ =& (a+c_{1}p)+((a^2+4b{)}^{\frac{p-1}{2}}+c_{2}p)\sqrt{a^2+4b}\\ =& a+(a^2+4b{)}^{\frac{p-1}{2}}\sqrt{a^2+4b}+c_{1}p+c_{2}p\sqrt{a^2+4b}\end{array}$$ 这时候因为$a^2+4b$是一个非二次剩余,所以上式可以表达为 $$a-\sqrt{a^2+4b}+c_{1}p+c_{2}p\sqrt{a^2+4b}$$ 我们让他乘上$\frac{a+\sqrt{a^2+4b}}{2}$,他的无理部就彻底与0同余了，此时的$n=(p+1)$,在让这个数幂上$p-1$，他的有理部就与1同余了，并且我们达到了之前的约定，n是p-1的倍数，此时的$n=(p+1)(p-1)$ #####两矩阵相等条件2: $$\begin{array}{rl}& {\lambda }^{n+1}=\lambda (k_{1}p+1)+k_{2}p\\ \iff & {\lambda }^{n+1}=(\frac{a}{2}+\frac{1}{2}\sqrt{a^2+4b})(k_{1}p+1)+k_{2}p\\ \iff & {\lambda }^{n+1}=(\frac{a}{2}+\frac{1}{2}\sqrt{a^2+4b})+\frac{a}{2}{k}_{1}p+\frac{1}{2}\sqrt{a^2+4b}{k}_{1}p{k}_{2}p+k_{2}p\end{array}$$ 之前我们证明了${\lambda }^{(p+1)(p-1)}$的有理部与1同余，无理部与0同余，这里显然${\lambda }^{(p+1)(p-1)+1}$的有理部与$\frac{a}{2}$同余，无理部与$\frac{1}{2}$同余, 至于${\lambda }_2$是同理的。

至此证明了当$a^2+4b$是二次剩余的时候,循环节至多为$n-1$,当$a^2+4b$不是二次剩余的时候，循环节至多为$n^2-1$ 当$a^2+4b=0$的时候还有待挖掘