皮萨诺周期

斐波那契数是指斐波那契数列中的数：

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, ... （OEIS数列A000045）

斐波那契数列由下方的递推关系定义

${\displaystyle F_{0}=0}$ 

${\displaystyle F_{1}=1}$ 

${\displaystyle F_{i}=F_{i-1}+F_{i-2}.}$ 

对于任意整数n, 数列{F_i (mod n)}为周期数列。皮萨诺周期π(n)记为该数列的周期。例如，模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, ... （OEIS数列A082115）

这一数列以8为周期，故π(3) = 8.

除去π(2) = 3 以外，皮萨诺周期必为偶数。这一性质的一个简单证明可由如下事实导出：

考虑斐波那契矩阵

${\displaystyle \mathbf {F} ={\begin{bmatrix}1&1\\1&0\end{bmatrix}}}$ 

则π(n)应等同于矩阵 F 在一般线性群GL₂(ℤ_n)的阶，其中GL₂(ℤ_n)表示在整数模 n 环上全体二阶可逆矩阵构成的乘法群。由于F的行列式为−1, 可知在ℤ_n中有(−1)^π(n) = 1, 故π(n)为偶数。^[3]

当 m,n 互质时，由中国剩余定理即知π(mn)等于π(m)和π(n)的最小公倍数。例如，π(3) = 8 而π(4) = 6，由此可得π(12) = 24. 因此，对皮萨诺周期的研究可以化归为对素数幂q = p^k (k ≥ 1) 的皮萨诺周期的研究。

可以证明，若p为素数，则π(p^k)整除p^k–1π(p). 有猜想认为${\displaystyle \pi (p^{k})=p^{k-1}\pi (p)}$ 对一切素数p及整数k > 1成立。任何不满足该猜想的素数p都必然是一个沃尔-孙-孙素数，而这种素数被猜想并不存在。

因此对皮萨诺周期的研究可以被进一步化归为对素数的皮萨诺周期的研究。出于这种考虑，需要特别指出两个反常的素数。素数2的皮萨诺周期为奇数，而素数5的皮萨诺周期和其他素数相比“大得多”。这两个素数的幂的皮萨诺周期为：

• 若 n = 2^k, 则 π(n) = 3·2^k–1 = 3n/2.
• 若 n = 5^k, 则 π(n) = 4·5^k = 4n.

由此可知对n = 2·5^k有π(n) = 6n.

2和5以外的所有素数均属于共轭类${\displaystyle p\equiv \pm 1{\pmod {10}}}$  或 ${\displaystyle p\equiv \pm 2{\pmod {5}}}$ . 在这一情况下，在模p下由比内公式的类比可知π(p) 是 x² – x – 1 的根模p的指数。当${\displaystyle p\equiv \pm 1{\pmod {10}}}$ 时，根据二次互反律，这两个根在 ${\displaystyle \mathbb {F} _{p}=\mathbb {Z} /p\mathbb {Z} }$  中，由费马小定理可知π(p)整除p – 1. 例如，π(11) = 11 – 1 = 10，π(29) = (29 – 1)/2 = 14.

若${\displaystyle p\equiv \pm 2{\pmod {5}},}$  根据二次互反律，x² – x – 1 的根不在${\displaystyle \mathbb {F} _{p}}$ 内，而是在有限域

${\displaystyle \mathbb {F} _{p}[x]/(x^{2}-x-1)}$ 

中。注意到弗罗贝尼乌斯自同态 ${\displaystyle x\mapsto x^{p}}$  将方程的两根r和s交换，因而r^p = s，故r^p+1 = –1. 由此可得r^2(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 · 5^r, r ≥ 1. 最小的两个等号成立的例子为 π(10) = 60 及 π(50) = 300. 若 n 不能表示为 2 · 5^r 的形式，则π(n) ≤ 4n.

前十二个自然数的皮萨诺周期（OEIS中的数列A001175）及其对应的一个周期内的所有数列举如下（为可读性起见，在每个0前加有空格；X, E分别表示10, 11）：^[4]

如果n = F (2k) (k ≥ 2), 那么π(n) = 4k; 如果n = F (2k + 1) (k ≥ 2), 那么π(n) = 8k + 4. 换而言之，模 F(2k) (k ≥ 2)的一个周期内有两个0，而模F (2k + 1) (k ≥ 2)的一个周期内有四个0.

• Engstrom, H. T. (1931). "On sequences defined by linear recurrence relations". Trans. Am. Math. Soc. 33 (1): 210–218. doi:10.1090/S0002-9947-1931-1501585-5. JSTOR 1989467. MR 1501585. 
• Freyd, Peter; Brown, Kevin S. (1992). "Problems and Solutions: Solutions: E3410". Amer. Math. Monthly 99 (3): 278–279. doi:10.2307/2325076. 
• Ward, Morgan (1931). "The characteristic number of a sequence of integers satisfying a linear recursion relation". Trans. Am. Math. Soc. 33 (1): 153–165. doi:10.1090/S0002-9947-1931-1501582-X. JSTOR 1989464. 
• Ward, Morgan (1933). "The arithmetical theory of linear recurring series". Trans. Am. Math. Soc. 35 (3): 600–628. doi:10.1090/S0002-9947-1933-1501705-4. JSTOR 1989851. 
• Zierler, Neal (1959). "Linear recurring sequences". J. SIAM 7 (1): 31–38. doi:10.1137/0107003. JSTOR 2099002. MR 0101979. 
• Wall, D. D. (1960). "Fibonacci series modulo m". Am. Math. Monthly 67 (6): 525—532. doi:10.2307/2309169. JSTOR 2309169. 
• Bloom, D. M. (1965). "Periodicity in generalized Fibonacci sequences". Am. Math. Monthly 72: 856—861. doi:10.2307/2315029. JSTOR 2315029. MR 0222015. 
• Laxton, R. R. (1969). "On groups of linear recurrences". Duke Mathematical Journal 36 (4): 721–736. doi:10.1215/S0012-7094-69-03687-4. MR 0258781. 
• Brent, Richard P. (1994). "On the periods of generalized Fibonacci sequences". Mathematics of Computation 63 (207): 389–401. arXiv:1004.5439. Bibcode:1994MaCom..63..389B （页面存档备份，存于互联网档案馆）. doi:10.2307/2153583. JSTOR 2153583. MR 1216256. 
• Johnson, R. C. (2008). "Fibonacci numbers and matrices" （页面存档备份，存于互联网档案馆） (PDF). 

1. ^ Weisstein, Eric W., "Pisano Period" （页面存档备份，存于互联网档案馆）, MathWorld.
2. ^ On Arithmetical functions related to the Fibonacci numbers （页面存档备份，存于互联网档案馆）.
3. ^ A Theorem on Modular Fibonacci Periodicity （页面存档备份，存于互联网档案馆）.
4. ^ Graph of the cycles modulo 1 to 24.