|
|
zh.wikipedia.org/wiki/皮萨诺周期
斐波那契数列 $\{F_i\}={}$0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584 ...
对于任意整数$n$, 数列$\{F_i\pmod n\}$为周期数列。皮萨诺周期$π(n)$记为该数列的周期。
例如，$\{F_i\pmod 3\}={}$0, 1, 1, 2, 0, 2, 2, 1, 0, 1, 1, 2, 0, 2, 2, 1, 0, 1, 1, 2, 0, 2, 2, 1, 0, ...
这一数列以8为周期，故$π(3) = 8$.
除去$π(2) = 3$以外，皮萨诺周期必为偶数。
证明考虑斐波那契矩阵$$ \mathbf {F} ={\begin{bmatrix}1&1\\1&0\end{bmatrix}} $$则$π(n)$应等同于矩阵 $\bf F$ 在一般线性群$GL_2(ℤ_n)$的阶，其中$GL_2(ℤ_n)$表示在整数模 $n$ 环上全体二阶可逆矩阵构成的乘法群。由于$\bf F$的行列式为$−1$, 可知在$ℤ_n$中有$(−1)^{π(n)}= 1$, 故$π(n)$为偶数。
当 $m,n$ 互质时，由中国剩余定理即知$π(mn)$等于$π(m)$和$π(n)$的最小公倍数。例如，$π(3) = 8$ 而 $π(4) = 6$，由此可得 $π(12) = 24$. 因此，对皮萨诺周期的研究可以化归为对素数幂 $q = p^k\ (k ≥ 1)$ 的皮萨诺周期的研究。
可以证明，若$p$为素数，则$π(p^k)$整除pk–1π(p). 有猜想认为$ \pi (p^{k})=p^{k-1}\pi (p) $对一切素数p及整数k > 1成立。任何不满足该猜想的素数$p$都必然是一个沃尔-孙-孙素数，而这种素数被猜想并不存在。
因此对皮萨诺周期的研究可以被进一步化归为对素数的皮萨诺周期的研究。出于这种考虑，需要特别指出两个反常的素数。素数2的皮萨诺周期为奇数，而素数5的皮萨诺周期和其他素数相比“大得多”。这两个素数的幂的皮萨诺周期为：
若 n = 2k, 則 π(n) = 3·2k–1 = 3n/2.
若 n = 5k, 則 π(n) = 4·5k = 4n.
由此可知对n = 2·5k有π(n) = 6n.
2和5以外的所有素数均属于共轭类$ p\equiv \pm 1{\pmod {10}} $ 或 $ p\equiv \pm 2{\pmod {5}} $. 在这一情况下，在模$p$下由比内公式的类比可知 $π(p)$ 是 $x^2-x-1$ 的根模 $p$ 的指数。当$ p\equiv \pm 1{\pmod {10}} $时，根据二次互反律，这两个根在 $ \mathbb {F} _{p}=\mathbb {Z} /p\mathbb {Z} $ 中，由费马小定理可知π(p)整除p – 1. 例如，π(11) = 11 – 1 = 10，π(29) = (29 – 1)/2 = 14.
若$ p\equiv \pm 2{\pmod {5}}, $ 根据二次互反律，$x^2-x-1$ 的根不在$ \mathbb {F} _{p} $内，而是在有限域
$ \mathbb {F} _{p}[x]/(x^{2}-x-1) $
中。注意到弗罗贝尼乌斯自同态 $ x\mapsto x^{p} $ 将方程的两根$r$和$s$交换，因而$r^p = s$，故$r^{p+1}= –1$. 由此可得r2(p+1) = 1, 故r的阶，也即π(p)，是2(p+1)除以某个奇数的商，因而必为4的倍数。在这种情况中，最小的三个满足 π(p)<2(p+1) 的例子为π(47) = 2(47 + 1)/3 = 32, π(107) = 2(107 + 1)/3 = 72 及π(113) = 2(113 + 1)/3 = 76.
据上述讨论，若 $n = p^k$ 是一个奇素数幂，满足π(n) > n, 则 π(n)/4 是一个不大于n的整数。利用皮萨诺周期的乘积性质，可得
π(n) ≤ 6n,
等号成立当且仅当n = 2 · 5r, r ≥ 1. 最小的两个等号成立的例子为 π(10) = 60 及 π(50) = 300. 若 n 不能表示为 2 · 5r 的形式，则π(n) ≤ 4n. |
|
