皮薩諾週期

在數論中，自然數 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]