皮薩諾周期

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

這一數列以8為周期，故Π(3) = 8.

## 性質

除去Π(2) = 3 以外，皮薩諾周期必為偶數。這一性質的一個簡單證明可由如下事實導出：

考慮斐波那契矩陣

$$\mathbf F = \begin{bmatrix} 1 & 1\\1 & 0 \end{bmatrix}$$

則π(n)應等同於矩陣 F 在一般線性群GL2(ℤn)的階，其中GL2(ℤn)表示在整數模 n 環上全體二階可逆矩陣構成的乘法群。由於F的行列式為−1, 可知在ℤn中有(−1)Π(n) = 1, 故Π(n)為偶數。

當 m,n 互質時，由中國剩餘定理即知Π(mn)等於Π(m)和Π(n)的最小公倍數。例如，Π(3) = 8 而Π(4) = 6，由此可得Π(12) = 24. 因此，對皮薩諾周期的研究可以化歸為對素數冪q = pk (k ≥ 1) 的皮薩諾周期的研究。

可以證明，若p為素數，則Π(pk)整除pk–1Π(p). 有猜想認為$\pi(p^k) = p^{k-1}\pi(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 \equiv \pm 1 \pmod {10}$ 或 $p \equiv \pm 2 \pmod {5}$. 在這一情況下，在模p下由比內公式的類比可知Π(p) 是 x2 – 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},$ 根據二次互反律，x2 – x – 1 的根不在$\mathbb{F}_{p}$內，而是在有限域

$$\mathbb{F}_{p}[x]/(x^2 - x - 1)$$

中。注意到弗羅貝尼烏斯自同態 $x \mapsto x^p$ 將方程的兩根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）：

n｜π(n)｜一個周期中0的數目｜一個周期中的所有數｜OEIS 中

1｜1｜1｜0

2｜3｜1｜011

3｜8｜2｜0112 0221

4｜6｜1｜011231

5｜20｜4｜01123 03314 04432 02241

6｜24｜2｜011235213415 055431453251

7｜16｜2｜01123516 06654261

8｜12｜2｜011235 055271

9｜24｜2｜011235843718 088764156281

10｜60｜4｜011235831459437 077415617853819 099875279651673 033695493257291

11｜10｜1｜01123582X1

12｜24｜2｜011235819X75 055X314592E1

π(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