数学学习笔记4
二阶递推数列
若一个递推式 $f_i=af_{i-1}+bf_{i-2}(0<a,b)$，那么这个递推式就是一个二阶递推数列。
我们以斐波那契数列为例来探讨一下某个特殊类型的二阶递推数列的性质。
$$
f_i=f_{i-1}+f_{i-2}
$$
通项公式（可由特征方程推出，此处不详细介绍）：
$$f_n=\dfrac{1}{\sqrt{5}}(\dfrac{(1+\sqrt{5})^n}{2^n}-\dfrac{(1-\sqrt{5})^n}{2^n})$$
性质
- 卡西尼性质：$f_{i-1}f_{i+1}-f_i^2=(-1)^i$。
- 附加性：$f_{n+k}=f_nf_{k-1}+f_{n+1}f_k$。
- $\forall k \in \mathbf{N},f_n \mid f_{nk}$。
- 若 $f_a \mid f_b$ 则 $a \mid b$。
- 最大公因数：$\gcd(f_a,f_b)=\gcd(a,b)$。
- 以斐波那契数列相邻两项作为输入会使欧几里德算法达到最坏复杂度。
求出第 $i$ 个值
我们可以用矩阵乘法，即：
$$\begin{bmatrix}f_i & f_{i+1}\end{bmatrix} \times \begin{bmatrix}0 & 1 \\ 1 & 1\end{bmatrix}=\begin{bmatrix}f_{i+1} & f_{i+2}\end{bmatrix}$$
时间复杂度可以看做是 $O(\log n)$。
特别的如果 $5$ 在 $\bmod$ 下有二次剩余的话，我们可以直接通过通项公式解决，时间复杂度是小常数的 $O(\log n)$。
求出值为 $x$ 的最前下标
即求出最小的 $i$ 使得 $f_i=x$。
首先这个情况必须满足 $5$ 有二次剩余，否则会很麻烦，此处假设 $5$ 有二次剩余。
下面令 $x \gets x \times \sqrt{5}$，通过通项公式计算，设 $A=\dfrac{(1+\sqrt{5})^n}{2^n},B=\dfrac{(1-\sqrt{5})^n}{2^n}$，那么有 $AB=(-1)^n$ 并且 $(A-B)^2=x^2$。
于是知二求一即可，分讨 $4$ 种情况，求一下二次剩余和 bsgs 即可。（可能还需要用到原根，详见笔记 1）
代码如下：
1 |
|
模意义下周期性
先说结论，如果 $\sqrt{5}$ 在模 $p$ 下有可以表示的数，那么周期一定整除 $p-1$，否则周期一定整除 $2p+2$。（$p$ 是大于 $5$ 的质数）
并且周期是一个环，不是 $\rho$ 形状的。
证明
设 $A=\dfrac{(1+\sqrt{5})^n}{2^n},B=\dfrac{(1-\sqrt{5})^n}{2^n}$，如果 $\sqrt{5} \in Z_p$，那么 $A \in Z_p,B \in Z_p$，根据费马小定理，那么 $A^p \equiv A,B^p \equiv B$，立即得 $d(p) \mid p-1$。
如果 $\sqrt{5} \not\in Z_p$，那么 $A,B \in Z_p[\sqrt{5}]$，此处涉及到“扩域”的知识，大概就是设 $z=ax+by$ 其中 $y=\sqrt{5}$，$z \in Z_p[\sqrt{5}]$，我们可以对于它定义加法乘法运算，并且满足交换律，结合律，分配律，故我们可以在这个域里面执行四则运算。
但是 $AB$ 仍然等于 $-1$，所以：
$$
\begin{aligned}
A^p &= (-BA)A^p\\
&=-A^{p+1}B\\
&=-B((\dfrac12)^2-(\dfrac{\sqrt{5}}{2})^2)\\
&=B
\end{aligned}
$$
解释一下为什么 $A^{p+1}=((\dfrac12)^2-(\dfrac{\sqrt{5}}{2})^2)$，首先我们知道 $A^{p-1}$ 因为 $5$ 在模 $p$ 意义下没有二次剩余，所以 $A^{p-1}$ 也没有可以表示出来的数，但是因为 $p$ 是奇素数，所以 $p-1$ 是偶数，那么 $\sqrt{5}^{p-1}=5^{\frac{p-1}{2}}$ 是可以表示出来的，它的平方就是 $5^{p-1}$，根据费马小定理可得 $5^{p-1} \equiv 1$，所以 $5^{\frac{p-1}{2}}=1$ 或者 $-1$，如果它等于 $1$，那么 $\sqrt{5}$ 就可以表示出来，所以它等于 $-1$。（需要二项式展开，此处略过）
欧拉准则
这里就可以推出来，如果 $p$ 是奇质数，那么当 $m^{\frac{p-1}{2}} \equiv 1$ 时，$m$ 有二次剩余，当它等于 $-1$ 时，$m$ 没有二次剩余。
所以 $A^{p-1}= -1$，所以 $A^{p+1} = -A^2=AB=((\dfrac12)^2-(\dfrac{\sqrt{5}}{2})^2)=-1$。
同理 $B^p=A$，所以 $A^{2p+3}=A^{2p+2}A=(-1)^2A=A$，于是找到一个循环节 $2p+2$。
证毕。
如果要找最小周期的话，像阶一样求解即可，但是判断的时候用矩阵乘法即可。
这个周期称作皮萨诺周期，如果我们要求其它数的周期的话，我们需要先分解，然后直接用 $\operatorname{lcm}$ 合并。
有性质 $d(p^k)=p \times d(p^{k-1})(2 \le k)$ 且 $p$ 是质数，特别的当 $p \le 5$ 的时候需要手动找循环节，$d(2)=3,d(3)=8,d(5)=20$。
那么合数的循环节也可以求了，并且可以证明 $d(m) \le 6m$，且只有在满足 $m=2\times 5^k$ 的形式时才取到等号。
特别的，如果是其它二阶递推我们把特征方程写出来之后也含有根号，如果这个根号能够在模 $p$ 意义下表示出来，也需要计算最小周期，不能认为周期一定是 $p-1$ 或者 $2p+2$。
寻找周期的代码（需要特判 $1 \le p \le 5$）：
1 |
|