皮萨诺周期
定义
斐波那契数是指斐波那契数列中的数:
斐波那契数列由下方的递推关系定义
对于任意整数n, 数列{Fi (mod n)}为周期数列. 皮萨诺周期π(n)记为该数列的周期. 例如,模3的斐波那契数列前若干项为:
这一数列以8为周期,故π(3) = 8.
性质
除去π(2) = 3 以外,皮萨诺周期必为偶数. 这一性质的一个简单证明可由如下事实导出:
考虑斐波那契矩阵
则π(n)应等同于矩阵 F 在一般线性群GL2(ℤn)的阶,其中GL2(ℤn)表示在整数模 n 环上全体二阶可逆矩阵构成的乘法群. 由于F的行列式为-1,可知在ℤn中有(-1) = 1, 故π(n)为偶数.
当m,n 互质时,由中国剩余定理即知π(mn)等于π(m)和π(n)的最小公倍数. 例如,π(3) = 8 而π(4) = 6,由此可得π(12) = 24. 因此,对皮萨诺周期的研究可以化归为对素数幂q = p(k ≥ 1)的皮萨诺周期的研究。
可以证明,若p为素数,则π(p)整除pπ(p).有猜想认为π π -->(pk)=pk− − -->1π π -->(p){\displaystyle \pi (p^{k})=p^{k-1}\pi (p)}对一切素数p及整数k > 1成立. 任何不满足该沃尔-孙-孙素数然是一个沃尔-孙-孙素数,而这种素数被猜想并不存在.
因此对皮萨诺周期的研究可以被进一步化归为对素数的皮萨诺周期的研究.出于这种考虑,需要特别指出两个反常的素数. 素数2的皮萨诺周期为奇数,而素数5的皮萨诺周期和其他素数相比“大得多”.这两个素数的幂的皮萨诺周期为:
If n = 2, then π(n) = 3·2 = 3n/2.
if n = 5, then π(n) = 4·5 = 4n.
由此可知对n = 2·5有π(n) = 6n.
2和5以外的所有素数均属于共轭类p≡ ≡ -->± ± -->1(mod10){\displaystyle p\equiv \pm 1{\pmod {10}}} 或 p≡ ≡ -->± ± -->2(mod5){\displaystyle p\equiv \pm 2{\pmod {5}}}. 比内一情况下,在模p下由比内公式的类比可知π(p) 是 x – x – 1 的根模p的指数. 当p≡ ≡ -->± ± -->1(mod10){\displaystyle p\equiv \pm 1{\pmod {10}}}时,根据二次互反律,这两个根在 Fp=Z/pZ{\displaystyle \mathbb {F} _{p}=\mathbb {Z} /p\mathbb {Z} } 中,由费马小定理可知π(p)整除p – 1. 例如,π(11) = 11 – 1 = 10,π(29) = (29 – 1)/2 = 14.
若p≡ ≡ -->± ± -->2(mod5),{\displaystyle p\equiv \pm 2{\pmod {5}},}根据二次互反律,x – x – 1 的根不在Fp{\displaystyle \mathbb {F} _{p}}内,而是在有限域
中.注意到弗罗贝尼乌斯自同态x↦ ↦ -->xp{\displaystyle x\mapsto x^{p}} 将方程的两根r和s交换,因而r = s,故r = –1. 由此可得r = 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是一个奇素数幂,满足π(n) > n, 则π(n)/4 是一个不大于n的整数. 利用皮萨诺周期的乘积性质,可得
等号成立当且仅当n = 2 · 5, r ≥ 1. 最小的两个等号成立的例子为π(10) = 60 及 π(50) = 300. 若 n 不能表示为 2 · 5 的形式,则π(n) ≤ 4n.
列表
前十二个自然数的皮萨诺周期(OEIS中的数列A001175)及其对应的一个周期内的所有数列举如下(为可读性起见,在每个0前加有空格;X,E分别表示10,11):
斐波那契数的皮萨诺周期
如果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.
参见
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.JSTOR1989467.MR1501585.
Freyd, Peter; Brown, Kevin S. (1992). "Problems and Solutions: Solutions: E3410". Amer. Math.Monthly99 (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.JSTOR1989464.
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.JSTOR1989851.
Zierler, Neal (1959). "Linear recurring sequences". J. SIAM7 (1): 31–38.doi:10.1137/0107003.JSTOR2099002.MR0101979.
Wall, D. D. (1960)."Fibonacci series modulo m". Am. Math. Monthly67 (6): 525—532.doi:10.2307/2309169.JSTOR2309169.
Bloom, D. M. (1965). "Periodicity in generalized Fibonacci sequences". Am. Math. Monthly72: 856—861.doi:10.2307/2315029.JSTOR2315029.MR0222015.
Laxton, R. R. (1969). "On groups of linear recurrences". Duke Mathematical Journal36 (4): 721–736.doi:10.1215/S0012-7094-69-03687-4.MR0258781.
Brent, Richard P. (1994). "On the periods of generalized Fibonacci sequences". Mathematics of Computation63 (207): 389–401.arXiv:1004.5439.Bibcode:1994MaCom..63..389B.doi:10.2307/2153583.JSTOR2153583.MR1216256.
Johnson, R. C. (2008)."Fibonacci numbers and matrices"(PDF).
免责声明:以上内容版权归原作者所有,如有侵犯您的原创版权请告知,我们将尽快删除相关内容。感谢每一位辛勤著写的作者,感谢每一位的分享。
- 有价值
- 一般般
- 没价值