皮薩諾週期
![本頁使用了標題或全文手工轉換](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).