thumb|300px|right|Plot of the first 10,000 Pisano periods.
In number theory, the nth Pisano period, written as '(n), is the period with which the sequence of Fibonacci numbers taken modulo n repeats. Pisano periods are named after Leonardo Pisano, better known as Fibonacci. The existence of periodic functions in Fibonacci numbers was noted by Joseph Louis Lagrange in 1774.
Definition
The Fibonacci numbers are the numbers in the integer sequence:
: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, ...
defined by the recurrence relation
:<math>F_0 = 0</math>
:<math>F_1 = 1</math>
:<math>F_i = F_{i-1} + F_{i-2}.</math>
For any integer n, the sequence of Fibonacci numbers F<sub>i</sub> taken modulo n is periodic.
The Pisano period, denoted '(n), is the length of the period of this sequence. For example, the sequence of Fibonacci numbers modulo 3 begins:
: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, ...
This sequence has period 8, so '(3) = 8.
thumb|For n = 3, this is a visualization of the Pisano period in the two-dimensional state space of the recurrence relation. The axes could also have been called "previous" and "current." The journey begins at (previous, current) = (0, 1) with red color, and then progresses through the colors of the rainbow eventually reaching (1, 0) and then returning to (0, 1). We see '(3) = 8.
Properties
Parity
With the exception of '(2) = 3, the Pisano period '(n) is always even.
This follows by observing that '(n) is equal to the order of the Fibonacci matrix
:<math>
\mathbf Q = \begin{bmatrix} 1 & 1\\1 & 0 \end{bmatrix}
</math>
in the general linear group <math>\text{GL}_2(\mathbb{Z}_n)</math>of invertible 2 by 2 matrices in the finite ring <math>\mathbb{Z}_n</math>of integers modulo n. Since Q has determinant −1, the determinant of Q<sup>'(n)</sup> is (−1)<sup>'(n)</sup>, which is equal to 1 when either n ≤ 2 or '(n) is even.
Pisano periods of composite numbers
If m and n are coprime, then '(mn) is the least common multiple of '(m) and '(n). This follows from Chinese remainder theorem.
Thus the Pisano periods of composite numbers can be computed by looking at the Pisano periods of prime powers q = p<sup>k</sup>, for k ≥ 1.
If p is prime, '(p<sup>k</sup>) divides p<sup>k–1</sup> '(p). It is unknown if
<math>
\pi(p^k) = p^{k-1}\pi(p)
</math>
for every prime p and integer k > 1. Any prime p providing a counterexample would necessarily be a Wall–Sun–Sun prime, and conversely every Wall–Sun–Sun prime p gives a counterexample (set k = 2).
For p = 2 and 5, the exact values of the Pisano periods are known. The periods of powers of these prime powers are as follows:
- If n = 2<sup>k</sup>, then <math>\pi(n) = 3 \cdot 2^{k-1} = \frac{3n}2</math>
- if n = 5<sup>k</sup>, then <math>\pi(n) = 4 \cdot 5^k = 4n</math>
From these it follows that if n = 2·5<sup>k</sup> then '(n) = 6n.
Pisano periods of prime numbers
thumb|State space visualization of the Pisano period for n = 5
thumb|State space visualization of the Pisano period for n = 10
If prime p is different from 2 and 5, then '(p) is a divisor of p<sup>2</sup> − 1. This follows from the modulo p analogue of Binet's formula, which implies that '(p) is the multiplicative order of a root of modulo p.
Every p other than 2 and 5 lie in the residue classes <math>p \equiv \pm 1\ (\mathrm{mod}\ 10)</math> or <math>p \equiv \pm 3\ (\mathrm{mod}\ 10)</math>.
- If <math>p \equiv \pm 1\ (\mathrm{mod}\ 10)</math>, then '(p) divides p − 1.
- If <math>p \equiv \pm 3\ (\mathrm{mod}\ 10)</math>, then '(p) divides 2(p + 1).
The former can be proven by observing that if <math>p \equiv \pm 1\ (\mathrm{mod}\ 10)</math>, then the roots of modulo p belong to <math>\mathbb{F}_{p} = \mathbb{Z}/p\mathbb{Z}</math> (by quadratic reciprocity). Thus their order, '(p) is a divisor of p − 1.
To prove the latter, if <math>p \equiv \pm 3\ (\mathrm{mod}\ 10),</math> the roots modulo p of do not belong to <math>\mathbb{F}_{p}</math> (by quadratic reciprocity again), and belong to the finite field <math>\mathbb{F}_{p}[x]/(x^2 - x - 1).</math> As the Frobenius automorphism <math>x \mapsto x^p</math> exchanges these roots, it follows that, denoting them by r and s, we have r<sup> p</sup> = s, and thus r<sup> p+1</sup> = –1. That is r<sup> 2(p+1)</sup> = 1, and the Pisano period, which is the order of r, is the quotient of 2(p + 1) by an odd divisor.
It follows from above results, that if n = p<sup>k</sup> is an odd prime power such that '(n) > n, then '(n)/4 is an integer that is not greater than n. The multiplicative property of Pisano periods imply thus that
:'(n) ≤ 6n, with equality if and only if n = 2 · 5<sup>r</sup>, for r ≥ 1.
If n is not of the form 2 · 5<sup>r</sup>, then '(n) ≤ 4n.
Tables
The first twelve Pisano periods and their cycles (with spaces before the zeros for readability) are (using X and E for ten and eleven, respectively):
{|class="wikitable"
!n!!π(n)!!number of zeros in the cycle ()!!cycle ()!!OEIS sequence for the cycle
|-
|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||
|}
The first 144 Pisano periods are shown in the following table:
{|class="wikitable"
!π(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
|}
Pisano periods of Fibonacci numbers
If n = F(2k) (k ≥ 2), then π(n) = 4k; if n = F(2k + 1) (k ≥ 2), then π(n) = 8k + 4. That is, if the modulo base is a Fibonacci number (≥ 3) with an even index, the period is twice the index and the cycle has two zeros. If the base is a Fibonacci number (≥ 5) with an odd index, the period is four times the index and the cycle has four zeros.
{|class="wikitable"
!k!!F(k)!!π(F(k))!!first half of cycle (for even k ≥ 4) or first quarter of cycle (for odd k ≥ 4) or all cycle (for k ≤ 3)<br>(with selected second halves or second quarters)
|-
|1||1||1||0
|-
|2||1||1||0
|-
|3||2||3||0, 1, 1
|-
|4||3||8||0, 1, 1, 2, (0, 2, 2, 1)
|-
|5||5||20||0, 1, 1, 2, 3, (0, 3, 3, 1, 4)
|-
|6||8||12||0, 1, 1, 2, 3, 5, (0, 5, 5, 2, 7, 1)
|-
|7||13||28||0, 1, 1, 2, 3, 5, 8, (0, 8, 8, 3, 11, 1, 12)
|-
|8||21||16||0, 1, 1, 2, 3, 5, 8, 13, (0, 13, 13, 5, 18, 2, 20, 1)
|-
|9||34||36||0, 1, 1, 2, 3, 5, 8, 13, 21, (0, 21, 21, 8, 29, 3, 32, 1, 33)
|-
|10||55||20||0, 1, 1, 2, 3, 5, 8, 13, 21, 34, (0, 34, 34, 13, 47, 5, 52, 2, 54, 1)
|-
|11||89||44||0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, (0, 55, 55, 21, 76, 8, 84, 3, 87, 1, 88)
|-
|12||144||24||0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, (0, 89, 89, 34, 123, 13, 136, 5, 141, 2, 143, 1)
|-
|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
|}
Pisano periods of Lucas numbers
If n = L(2k) (k ≥ 1), then π(n) = 8k; if n = L(2k + 1) (k ≥ 1), then π(n) = 4k + 2. That is, if the modulo base is a Lucas number (≥ 3) with an even index, the period is four times the index. If the base is a Lucas number (≥ 4) with an odd index, the period is twice the index.
{|class="wikitable"
!k!!L(k)!!π(L(k))!!first half of cycle (for odd k ≥ 2) or first quarter of cycle (for even k ≥ 2) or all cycle (for k = 1)<br>(with selected second halves or second quarters)
|-
|1||1||1||0
|-
|2||3||8||0, 1, (1, 2)
|-
|3||4||6||0, 1, 1, (2, 3, 1)
|-
|4||7||16||0, 1, 1, 2, (3, 5, 1, 6)
|-
|5||11||10||0, 1, 1, 2, 3, (5, 8, 2, 10, 1)
|-
|6||18||24||0, 1, 1, 2, 3, 5, (8, 13, 3, 16, 1, 17)
|-
|7||29||14||0, 1, 1, 2, 3, 5, 8, (13, 21, 5, 26, 2, 28, 1)
|-
|8||47||32||0, 1, 1, 2, 3, 5, 8, 13, (21, 34, 8, 42, 3, 45, 1, 46)
|-
|9||76||18||0, 1, 1, 2, 3, 5, 8, 13, 21, (34, 55, 13, 68, 5, 73, 2, 75, 1)
|-
|10||123||40||0, 1, 1, 2, 3, 5, 8, 13, 21, 34, (55, 89, 21, 110, 8, 118, 3, 121, 1, 122)
|-
|11||199||22||0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, (89, 144, 34, 178, 13, 191, 5, 196, 2, 198, 1)
|-
|12||322||48||0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, (144, 233, 55, 288, 21, 309, 8, 317, 3, 320, 1, 321)
|-
|13||521||26||0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144
|-
|14||843||56||0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233
|-
|15||1364||30||0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377
|-
|16||2207||64||0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610
|-
|17||3571||34||0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987
|-
|18||5778||72||0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597
|-
|19||9349||38||0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584
|-
|20||15127||80||0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181
|-
|21||24476||42||0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765
|-
|22||39603||88||0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946
|-
|23||64079||46||0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711
|-
|24||103682||96||0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657
|}
For even k, the cycle has two zeros. For odd k, the cycle has only one zero, and the second half of the cycle, which is of course equal to the part on the left of 0, consists of alternatingly numbers F(2m + 1) and n − F(2m), with m decreasing.
Number of zeros in the cycle
The number of occurrences of 0 per cycle is 1, 2, or 4. Let p be the number after the first 0 after the combination 0, 1. Let the distance between the 0s be q.
- There is one 0 in a cycle, obviously, if p = 1. This is only possible if q is even or n is 1 or 2.
- Otherwise there are two 0s in a cycle if p<sup>2</sup> ≡ 1. This is only possible if q is even.
- Otherwise there are four 0s in a cycle. This is the case if q is odd and n is not 1 or 2.
For generalized Fibonacci sequences (satisfying the same recurrence relation, but with other initial values, e.g. the Lucas numbers) the number of occurrences of 0 per cycle is 0, 1, 2, or 4.
The ratio of the Pisano period of n and the number of zeros modulo n in the cycle gives the rank of apparition or Fibonacci entry point of n. That is, smallest index k such that n divides F(k). They are:
:1, 3, 4, 6, 5, 12, 8, 6, 12, 15, 10, 12, 7, 24, 20, 12, 9, 12, 18, 30, 8, 30, 24, 12, 25, 21, 36, 24, 14, 60, 30, 24, 20, 9, 40, 12, 19, 18, 28, 30, 20, 24, 44, 30, 60, 24, 16, 12, ...
In Renault's paper the number of zeros is called the "order" of F mod m, denoted <math>\omega(m)</math>, and the "rank of apparition" is called the "rank" and denoted <math>\alpha(m)</math>.
According to Wall's conjecture, <math>\alpha(p^e) = p^{e-1} \alpha(p)</math>. If <math>m</math> has prime factorization <math>m = p_1^{e_1} p_2^{e_2} \dots p_n^{e_n}</math> then <math>\alpha(m) = \operatorname{lcm}(\alpha(p_1^{e_1}), \alpha(p_2^{e_2}), \dots, \alpha(p_n^{e_n}))</math>.