皮萨诺周期

在数论中，自然数 *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, ... 

斐波那契数列由下方的递推关系定义
: F_0 = 0
: F_1 = 1
: F_i = F_{i-1} + F_{i-2}.
对于任意整数*n*, 数列{*F<sub>i</sub>* (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, ... 
这一数列以8为周期，故**'(3) = 8.

## 性质
除去**'(2) =&nbsp;3 以外，皮萨诺周期必为偶数。这一性质的一个简单证明可由如下事实导出：

考虑斐波那契矩阵
: <math>
\mathbf F = \begin{bmatrix} 1 & 1\\1 & 0 \end{bmatrix} 
</math>
则π(n)应等同于矩阵 **F **在一般线性群''GL''<sub>2</sub>(ℤ<sub>''n''</sub>)的阶，其中''GL''<sub>2</sub>(ℤ<sub>''n''</sub>)表示在整数模 ''n ''环上全体二阶可逆矩阵构成的乘法群。由于**F**的行列式为−1, 可知在ℤ<sub>n</sub>中有(−1)<sup>**'(n)&nbsp;=&nbsp;1, 故**'(n)为偶数。

当 ''m,n'' 互质时，由[[中国剩余定理]]即知**'(*mn*)等于**'(''m'')和**'(*n*)的最小公倍数。例如，**'(3) = 8 而**'(4) = 6，由此可得**'(12) = 24. 因此，对皮萨诺周期的研究可以化归为对[[素数幂]]''q'' = ''p''<sup>''k ''</sup> (''k'' ≥ 1) 的皮萨诺周期的研究。

可以证明，若''p''为素数，则**'(*p**k*)整除*p**k*–1**'(''p''). 有猜想认为<math>
\pi(p^k) = p^{k-1}\pi(p)
</math>对一切素数''p''及整数''k'' > 1成立。任何不满足该猜想的素数''p''都必然是一个[[沃尔-孙-孙素数]]，而这种素数被猜想并不存在。

因此对皮萨诺周期的研究可以被进一步化归为对素数的皮萨诺周期的研究。出于这种考虑，需要特别指出两个反常的素数。素数2的皮萨诺周期为奇数，而素数5的皮萨诺周期和其他素数相比“大得多”。这两个素数的幂的皮萨诺周期为：

* 若 ''n'' = 2<sup>''k''</sup>, 則 **'(*n*) = 3·2*k*–1 = 3*n*/2.
* 若 *n* = 5*k*, 則 **'(''n'') = 4·5<sup>''k''</sup> = 4''n''.
由此可知对''n'' = 2·5<sup>''k''</sup>有**'(*n*) = 6*n*.

2和5以外的所有素数均属于共轭类p \equiv \pm 1 \pmod {10} 或 p \equiv \pm 2 \pmod {5}. 在这一情况下，在模p下由比内公式的类比可知**'(''p'') 是 <span class="texhtml ">''x''<sup>2</sup> – ''x'' – 1 </span>的根模''p''的指数。当<math>p \equiv \pm 1 \pmod {10}</math>时，根据二次互反律，这两个根在 <math>\mathbb{F}_{p} = \mathbb{Z}/p\mathbb{Z}</math> 中，由[[费马小定理]]可知**'(*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*) &#x2264; 6*n*,
等号成立当且仅当*n*&nbsp;=&nbsp;2&nbsp;·&nbsp;5*r*, *r*&nbsp;≥&nbsp;1. 最小的两个等号成立的例子为 **'(10)&nbsp;=&nbsp;60 及 **'(50)&nbsp;=&nbsp;300. 若 *n* 不能表示为 2&nbsp;·&nbsp;5*r * 的形式，则**'(''n'') &#x2264; 4''n''.

== 列表 ==
前十二个自然数的皮萨诺周期（[[整數數列線上大全|OEIS]]中的数列）及其对应的一个周期内的所有数列举如下（为可读性起见，在每个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.


== 參考文獻 ==
* <cite class="citation journal" contenteditable="false">Engstrom, H. T. (1931). "On sequences defined by linear recurrence relations". ''Trans. Am. Math. Soc.'' **33** (1): 210–218. [[DOI|doi]]:. [[JSTOR]]&nbsp;[//www.jstor.org/stable/1989467 1989467]. </cite><cite class="citation journal" contenteditable="false">[[數學評論|MR]]&nbsp;[//www.ams.org/mathscinet-getitem?mr=1501585 1501585].</cite><span class="Z3988" title="ctx_ver=Z39.88-2004&rfr_id=info%3Asid%2Fen.wikipedia.org%3APisano+period&rft.atitle=On+sequences+defined+by+linear+recurrence+relations&rft.aufirst=H.+T.&rft.aulast=Engstrom&rft.date=1931&rft.genre=article&rft_id=%2F%2Fwww.ams.org%2Fmathscinet-getitem%3Fmr%3D1501585&rft_id=%2F%2Fwww.jstor.org%2Fstable%2F1989467&rft_id=info%3Adoi%2F10.1090%2FS0002-9947-1931-1501585-5&rft.issue=1&rft.jtitle=Trans.+Am.+Math.+Soc.&rft.pages=210-218&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.volume=33" contenteditable="false">&nbsp;</span>
* <cite class="citation journal" contenteditable="false">Freyd, Peter; Brown, Kevin S. (1992). "Problems and Solutions: Solutions: E3410". ''Amer. Math. ''</cite><cite class="citation journal" contenteditable="false">''Monthly'' **99** (3): 278–279. [[DOI|doi]]:.</cite><span class="Z3988" title="ctx_ver=Z39.88-2004&rfr_id=info%3Asid%2Fen.wikipedia.org%3APisano+period&rft.atitle=Problems+and+Solutions%3A+Solutions%3A+E3410&rft.au=Brown%2C+Kevin+S.&rft.aufirst=Peter&rft.aulast=Freyd&rft.date=1992&rft.genre=article&rft_id=info%3Adoi%2F10.2307%2F2325076&rft.issue=3&rft.jtitle=Amer.+Math.+Monthly&rft.pages=278-279&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.volume=99" contenteditable="false">&nbsp;</span>
* <cite class="citation journal" contenteditable="false">Ward, Morgan (1931). "The characteristic number of a sequence of integers satisfying a linear recursion relation". ''Trans. Am. Math. ''</cite><cite class="citation journal" contenteditable="false">''Soc.'' **33** (1): 153–165. [[DOI|doi]]:. [[JSTOR]]&nbsp;[//www.jstor.org/stable/1989464 1989464].</cite><span class="Z3988" title="ctx_ver=Z39.88-2004&rfr_id=info%3Asid%2Fen.wikipedia.org%3APisano+period&rft.atitle=The+characteristic+number+of+a+sequence+of+integers+satisfying+a+linear+recursion+relation&rft.aufirst=Morgan&rft.aulast=Ward&rft.date=1931&rft.genre=article&rft_id=%2F%2Fwww.jstor.org%2Fstable%2F1989464&rft_id=info%3Adoi%2F10.1090%2FS0002-9947-1931-1501582-X&rft.issue=1&rft.jtitle=Trans.+Am.+Math.+Soc.&rft.pages=153-165&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.volume=33" contenteditable="false">&nbsp;</span>
* <cite class="citation journal" contenteditable="false">Ward, Morgan (1933). "The arithmetical theory of linear recurring series". ''Trans. Am. Math. Soc.'' **35** (3): 600–628. [[DOI|doi]]:. </cite><cite class="citation journal" contenteditable="false">[[JSTOR]]&nbsp;[//www.jstor.org/stable/1989851 1989851].</cite><span class="Z3988" title="ctx_ver=Z39.88-2004&rfr_id=info%3Asid%2Fen.wikipedia.org%3APisano+period&rft.atitle=The+arithmetical+theory+of+linear+recurring+series&rft.aufirst=Morgan&rft.aulast=Ward&rft.date=1933&rft.genre=article&rft_id=%2F%2Fwww.jstor.org%2Fstable%2F1989851&rft_id=info%3Adoi%2F10.1090%2FS0002-9947-1933-1501705-4&rft.issue=3&rft.jtitle=Trans.+Am.+Math.+Soc.&rft.pages=600-628&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.volume=35" contenteditable="false">&nbsp;</span>
* <cite class="citation journal" contenteditable="false">Zierler, Neal (1959). "Linear recurring sequences". ''J. SIAM'' **7** (1): 31–38. [[DOI|doi]]:. [[JSTOR]]&nbsp;[//www.jstor.org/stable/2099002 2099002]. </cite><cite class="citation journal" contenteditable="false">[[數學評論|MR]]&nbsp;[//www.ams.org/mathscinet-getitem?mr=0101979 0101979].</cite><span class="Z3988" title="ctx_ver=Z39.88-2004&rfr_id=info%3Asid%2Fen.wikipedia.org%3APisano+period&rft.atitle=Linear+recurring+sequences&rft.aufirst=Neal&rft.aulast=Zierler&rft.date=1959&rft.genre=article&rft_id=%2F%2Fwww.ams.org%2Fmathscinet-getitem%3Fmr%3D0101979&rft_id=%2F%2Fwww.jstor.org%2Fstable%2F2099002&rft_id=info%3Adoi%2F10.1137%2F0107003&rft.issue=1&rft.jtitle=J.+SIAM&rft.pages=31-38&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.volume=7" contenteditable="false">&nbsp;</span>
* <cite class="citation journal" contenteditable="false">Wall, D. D. (1960). </cite><cite class="citation journal" contenteditable="false">"Fibonacci series modulo m". ''Am. Math. Monthly'' **67** (6): 525&#x2014;532. [[DOI|doi]]:. </cite><cite class="citation journal" contenteditable="false">[[JSTOR]]&nbsp;[//www.jstor.org/stable/2309169 2309169].</cite><span class="Z3988" title="ctx_ver=Z39.88-2004&rfr_id=info%3Asid%2Fen.wikipedia.org%3APisano+period&rft.atitle=Fibonacci+series+modulo+m&rft.aufirst=D.+D.&rft.aulast=Wall&rft.date=1960&rft.genre=article&rft_id=%2F%2Fwww.jstor.org%2Fstable%2F2309169&rft_id=info%3Adoi%2F10.2307%2F2309169&rft.issue=6&rft.jtitle=Am.+Math.+Monthly&rft.pages=525-532&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.volume=67" contenteditable="false">&nbsp;</span>
* <cite class="citation journal" contenteditable="false">Bloom, D. M. (1965). "Periodicity in generalized Fibonacci sequences". ''Am. Math. Monthly'' **72**: 856&#x2014;861. [[DOI|doi]]:. [[JSTOR]]&nbsp;[//www.jstor.org/stable/2315029 2315029]. </cite><cite class="citation journal" contenteditable="false">[[數學評論|MR]]&nbsp;[//www.ams.org/mathscinet-getitem?mr=0222015 0222015].</cite><span class="Z3988" title="ctx_ver=Z39.88-2004&rfr_id=info%3Asid%2Fen.wikipedia.org%3APisano+period&rft.atitle=Periodicity+in+generalized+Fibonacci+sequences&rft.aufirst=D.+M.&rft.aulast=Bloom&rft.date=1965&rft.genre=article&rft_id=%2F%2Fwww.ams.org%2Fmathscinet-getitem%3Fmr%3D0222015&rft_id=%2F%2Fwww.jstor.org%2Fstable%2F2315029&rft_id=info%3Adoi%2F10.2307%2F2315029&rft.jtitle=Am.+Math.+Monthly&rft.pages=856-861&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.volume=72" contenteditable="false">&nbsp;</span>
* <cite class="citation journal" contenteditable="false">Laxton, R. R. (1969). "On groups of linear recurrences". ''Duke Mathematical Journal'' **36** (4): 721–736. [[DOI|doi]]:. </cite><cite class="citation journal" contenteditable="false">[[數學評論|MR]]&nbsp;[//www.ams.org/mathscinet-getitem?mr=0258781 0258781].</cite><span class="Z3988" title="ctx_ver=Z39.88-2004&rfr_id=info%3Asid%2Fen.wikipedia.org%3APisano+period&rft.atitle=On+groups+of+linear+recurrences&rft.aufirst=R.+R.&rft.aulast=Laxton&rft.date=1969&rft.genre=article&rft_id=%2F%2Fwww.ams.org%2Fmathscinet-getitem%3Fmr%3D0258781&rft_id=info%3Adoi%2F10.1215%2FS0012-7094-69-03687-4&rft.issue=4&rft.jtitle=Duke+Mathematical+Journal&rft.pages=721-736&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.volume=36" contenteditable="false">&nbsp;</span>
* <cite class="citation journal" contenteditable="false">Brent, Richard P. (1994). "On the periods of generalized Fibonacci sequences". ''Mathematics of Computation'' **63''' (207): 389–401. arXiv:[//arxiv.org/abs/1004.5439 1004.5439]. Bibcode:1994MaCom..63..389B . doi:. JSTOR&nbsp;[//www.jstor.org/stable/2153583 2153583]. MR&nbsp;[//www.ams.org/mathscinet-getitem?mr=1216256 1216256].&nbsp;
* Johnson, R. C. (2008). "Fibonacci numbers and matrices"  (PDF).&nbsp;