皮萨诺周期
![本页使用了标题或全文手工转换](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
在数论中,自然数 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)
斐波那契数列由下方的递推关系定义
对于任意整数n, 数列{Fi (mod n)}为周期数列。皮萨诺周期π(n)记为该数列的周期。例如,模3的斐波那契数列前若干项为:
这一数列以8为周期,故π(3) = 8.
性质
除去π(2) = 3 以外,皮萨诺周期必为偶数。这一性质的一个简单证明可由如下事实导出:
考虑斐波那契矩阵
则π(n)应等同于矩阵 F 在一般线性群GL2(ℤn)的阶,其中GL2(ℤn)表示在整数模 n 环上全体二阶可逆矩阵构成的乘法群。由于F的行列式为−1, 可知在ℤn中有(−1)π(n) = 1, 故π(n)为偶数。[3]
当 m,n 互质时,由中国剩余定理即知π(mn)等于π(m)和π(n)的最小公倍数。例如,π(3) = 8 而π(4) = 6,由此可得π(12) = 24. 因此,对皮萨诺周期的研究可以化归为对素数幂q = pk (k ≥ 1) 的皮萨诺周期的研究。
可以证明,若p为素数,则π(pk)整除pk–1π(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下由比内公式的类比可知π(p) 是 x2 – x – 1 的根模p的指数。当时,根据二次互反律,这两个根在 中,由费马小定理可知π(p)整除p – 1. 例如,π(11) = 11 – 1 = 10,π(29) = (29 – 1)/2 = 14.
若 根据二次互反律,x2 – x – 1 的根不在内,而是在有限域
中。注意到弗罗贝尼乌斯自同态 将方程的两根r和s交换,因而rp = s,故rp+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 = pk是一个奇素数幂,满足π(n) > n, 则 π(n)/4 是一个不大于n的整数。利用皮萨诺周期的乘积性质,可得
- π(n) ≤ 6n,
等号成立当且仅当n = 2 · 5r, r ≥ 1. 最小的两个等号成立的例子为 π(10) = 60 及 π(50) = 300. 若 n 不能表示为 2 · 5r 的形式,则π(n) ≤ 4n.
列表
前十二个自然数的皮萨诺周期(OEIS中的数列A001175)及其对应的一个周期内的所有数列举如下(为可读性起见,在每个0前加有空格;X, E分别表示10, 11):[4]
n | π(n) | 一个周期中0的数目 (![]() |
一个周期中的所有数(![]() |
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).