皮萨诺周期

在数论中，自然数 n 的皮萨诺周期（通常记为π(n)）是斐波那契数列模 n 后的周期，以意大利数学家莱昂纳多·皮萨诺（即斐波那契）的名字命名。斐波那契数列取模后，周期的存在性曾在1774年为约瑟夫·拉格朗日所提及。^[1]^[2]

定义

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）

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

F_{0}=0

F_{1}=1

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 以外，皮萨诺周期必为偶数。这一性质的一个简单证明可由如下事实导出：

考虑斐波那契矩阵

\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). 有猜想认为 $\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以外的所有素数均属于共轭类 $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. 由此可得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	π(n)	一个周期中0的数目 ( A001176)	一个周期中的所有数( A161553)	OEIS 中
1	1	1	0	A000004
2	3	1	011	A011655
3	8	2	0112 0221	A082115
4	6	1	011231	A079343
5	20	4	01123 03314 04432 02241	A082116
6	24	2	011235213415 055431453251	A082117
7	16	2	01123516 06654261	A105870
8	12	2	011235 055271	A079344
9	24	2	011235843718 088764156281	A007887
10	60	4	011235831459437 077415617853819 099875279651673 033695493257291	A003893
11	10	1	01123582X1	A105955
12	24	2	011235819X75 055X314592E1	A089911

π(n)	+1	+2	+3	+4	+5	+6	+7	+8	+9	+10	+11	+12
0+	1	3	8	6	20	24	16	12	24	60	10	24
12+	28	48	40	24	36	24	18	60	16	30	48	24
24+	100	84	72	48	14	120	30	48	40	36	80	24
36+	76	18	56	60	40	48	88	30	120	48	32	24
48+	112	300	72	84	108	72	20	48	72	42	58	120
60+	60	30	48	96	140	120	136	36	48	240	70	24
72+	148	228	200	18	80	168	78	120	216	120	168	48
84+	180	264	56	60	44	120	112	48	120	96	180	48
96+	196	336	120	300	50	72	208	84	80	108	72	72
108+	108	60	152	48	76	72	240	42	168	174	144	120
120+	110	60	40	30	500	48	256	192	88	420	130	120
132+	144	408	360	36	276	48	46	240	32	210	140	24

斐波那契数的皮萨诺周期

如果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.

k	F (k)	π(F (k))	截至首个0出现前的一个（对 k ≤ 3）或一半(对不小于4的偶数k)、四分之一个（对不小于4的奇数k）周期
1	1	1	0
2	1	1	0
3	2	3	0, 1, 1
4	3	8	0, 1, 1, 2
5	5	20	0, 1, 1, 2, 3
6	8	12	0, 1, 1, 2, 3, 5
7	13	28	0, 1, 1, 2, 3, 5, 8
8	21	16	0, 1, 1, 2, 3, 5, 8, 13
9	34	36	0, 1, 1, 2, 3, 5, 8, 13, 21
10	55	20	0, 1, 1, 2, 3, 5, 8, 13, 21, 34
11	89	44	0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55
12	144	24	0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89
13	233	52	0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144
14	377	28	0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233
15	610	60	0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377
16	987	32	0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610
17	1597	68	0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987
18	2584	36	0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597
19	4181	76	0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584
20	6765	40	0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181
21	10946	84	0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765
22	17711	44	0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946
23	28657	92	0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711
24	46368	48	0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657

参考文献

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).

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

[mathworld-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.

[1]

[2]

[3]

[4]