皮萨诺周期

在數論中，自然數 _n_ 的**皮薩諾週期**（通常記為 π(_n_)）是費氏數列模 _n_ 後的週期，以義大利數學家萊昂納多・皮薩諾（即斐波那契）的名字命名。費氏數列取模後，週期的存在性曾在 1774 年為約瑟夫・拉格朗日所提及。

## 定義

費氏數列是：

　
: 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_, 數列 {_Fi_ (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_2(ℤn) 的階，其中 _GL_2(ℤn) 表示在整數模 _n_ 環上全體二階可逆矩陣構成的乘法群。由於 **F** 的行列式為−1, 可知在ℤn 中有 (−1)π(n)= 1, 故 _π_(n) 為偶數。

當 _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_ = 2k, 則 _π_(_n_) = 3·2k–1 = 3_n_/2.
* 若 _n_ = 5k, 則 _π_(_n_) = 4·5k = 4_n_.

由此可知對 _n_ = 2·5k 有 _π_(_n_) = 6_n_.

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_) ≤ 6_n_,

等號成立若且唯若 _n_ = 2 · 5r, _r_≥ 1. 最小的兩個等號成立的例子為 _π_(10) = 60 及 _π_(50) = 300. 若 _n_ 不能表示為 2 ・ 5r 的形式，則 _π_(_n_) ≤ 4_n_.

## 列表

前十二個自然數的皮薩諾週期（OEIS 中的數列 A001175）及其對應的一個週期內的所有數列舉如下（為可讀性起見，在每個 0 前加有空格；X, E 分別表示 10, 11）：

## 斐波那契數的皮薩諾週期

如果 _n_ = _F_ (2_k_) (_k_ ≥ 2), 那麼 π(_n_) = 4_k_; 如果 _n_ = _F_ (2_k_ + 1) (_k_ ≥ 2), 那麼 π(_n_) = 8_k_ + 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).