Pisano period

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, ... (sequence A000045 in the OEIS)

defined by the recurrence relation

${\displaystyle F_{0}=0}$

${\displaystyle F_{1}=1}$

${\displaystyle F_{i}=F_{i-1}+F_{i-2}.}$

For any integer n, the sequence of Fibonacci numbers F_i 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, ... (sequence A082115 in the OEIS)

This sequence has period 8, so π(3) = 8.

With the exception of π(2) = 3, the Pisano period π(n) is always even. A simple proof of this can be given by observing that π(n) is equal to the order of the Fibonacci matrix.

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

in the general linear group GL₂(ℤ_n) of invertible 2 by 2 matrices in the finite ring ℤ_n of integers modulo n. Since Q has determinant −1, the determinant of Q^π(n) is (−1)^π(n), and since this must equal 1 in ℤ_n, either n ≤ 2 or π(n) is even.[3]

If m and n are coprime, then π(mn) is the least common multiple of π(m) and π(n), by the Chinese remainder theorem. For example, π(3) = 8 and π(4) = 6 imply π(12) = 24. Thus the study of Pisano periods may be reduced to that of Pisano periods of prime powers q = p^k, for k ≥ 1.

If p is prime, π(p^k) divides p^k–1 π(p). It is unknown if ${\displaystyle \pi (p^{k})=p^{k-1}\pi (p)}$ 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).

So the study of Pisano periods may be further reduced to that of Pisano periods of primes. In this regard, two primes are anomalous. The prime 2 has an odd Pisano period, and the prime 5 has period that is relatively much larger than the Pisano period of any other prime. The periods of powers of these primes are as follows:

• If n = 2^k, then π(n) = 3·2^k–1 = 3·2^k/2 = 3n/2.
• if n = 5^k, then π(n) = 20·5^k–1 = 20·5^k/5 = 4n.

From these it follows that if n = 2 · 5^k then π(n) = 6n.

The remaining primes all lie in the residue classes ${\displaystyle p\equiv \pm 1{\pmod {10}}}$ or ${\displaystyle p\equiv \pm 3{\pmod {10}}}$. If p is a prime different from 2 and 5, then the modulo p analogue of Binet's formula implies that π(p) is the multiplicative order of the roots of x² − x − 1 modulo p. If ${\displaystyle p\equiv \pm 1{\pmod {10}}}$, these roots belong to ${\displaystyle \mathbb {F} _{p}=\mathbb {Z} /p\mathbb {Z} }$ (by quadratic reciprocity). Thus their order, π(p) is a divisor of p − 1. For example, π(11) = 11 − 1 = 10 and π(29) = (29 − 1)/2 = 14.

If ${\displaystyle p\equiv \pm 3{\pmod {10}},}$ the roots modulo p of x² − x − 1 do not belong to ${\displaystyle \mathbb {F} _{p}}$ (by quadratic reciprocity again), and belong to the finite field

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

As the Frobenius automorphism ${\displaystyle x\mapsto x^{p}}$ exchanges these roots, it follows that, denoting them by r and s, we have r^p = s, and thus r^p+1 = –1. That is r^2(p+1) = 1, and the Pisano period, which is the order of r, is the quotient of 2(p+1) by an odd divisor. This quotient is always a multiple of 4. The first examples of such a p, for which π(p) is smaller than 2(p+1), are π(47) = 2(47 + 1)/3 = 32, π(107) = 2(107 + 1)/3 = 72 and π(113) = 2(113 + 1)/3 = 76. (See the table below)

It follows from above results, that if n = p^k 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^r, for r ≥ 1.[4]

The first examples are π(10) = 60 and π(50) = 300. If n is not of the form 2 · 5^r, then π(n) ≤ 4n.

The first twelve Pisano periods (sequence A001175 in the OEIS) and their cycles (with spaces before the zeros for readability) are[5] (using hexadecimal cyphers A and B for ten and eleven, respectively):

The first 144 Pisano periods are shown in the following table:

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.

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.

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.

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² ≡ 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, ... (sequence A001177 in the OEIS)

In Renault's paper the number of zeros is called the "order" of F mod m, denoted ${\displaystyle \omega (m)}$, and the "rank of apparition" is called the "rank" and denoted ${\displaystyle \alpha (m)}$.[6]

According to Wall's conjecture, ${\displaystyle \alpha (p^{e})=p^{e-1}\alpha (p)}$. If ${\displaystyle m}$ has prime factorization ${\displaystyle m=p_{1}^{e_{1}}p_{2}^{e_{2}}\dots p_{n}^{e_{n}}}$ then ${\displaystyle \alpha (m)=\operatorname {lcm} (\alpha (p_{1}^{e_{1}}),\alpha (p_{2}^{e_{2}}),\dots ,\alpha (p_{n}^{e_{n}}))}$.[6]

The Pisano periods of Lucas numbers are

1, 3, 8, 6, 4, 24, 16, 12, 24, 12, 10, 24, 28, 48, 8, 24, 36, 24, 18, 12, 16, 30, 48, 24, 20, 84, 72, 48, 14, 24, 30, 48, 40, 36, 16, 24, 76, 18, 56, 12, 40, 48, 88, 30, 24, 48, 32, ... (sequence A106291 in the OEIS)

The Pisano periods of Pell numbers (or 2-Fibonacci numbers) are

1, 2, 8, 4, 12, 8, 6, 8, 24, 12, 24, 8, 28, 6, 24, 16, 16, 24, 40, 12, 24, 24, 22, 8, 60, 28, 72, 12, 20, 24, 30, 32, 24, 16, 12, 24, 76, 40, 56, 24, 10, 24, 88, 24, 24, 22, 46, 16, ... (sequence A175181 in the OEIS)

The Pisano periods of 3-Fibonacci numbers are

1, 3, 2, 6, 12, 6, 16, 12, 6, 12, 8, 6, 52, 48, 12, 24, 16, 6, 40, 12, 16, 24, 22, 12, 60, 156, 18, 48, 28, 12, 64, 48, 8, 48, 48, 6, 76, 120, 52, 12, 28, 48, 42, 24, 12, 66, 96, 24, ... (sequence A175182 in the OEIS)

The Pisano periods of Jacobsthal numbers (or (1,2)-Fibonacci numbers) are

1, 1, 6, 2, 4, 6, 6, 2, 18, 4, 10, 6, 12, 6, 12, 2, 8, 18, 18, 4, 6, 10, 22, 6, 20, 12, 54, 6, 28, 12, 10, 2, 30, 8, 12, 18, 36, 18, 12, 4, 20, 6, 14, 10, 36, 22, 46, 6, ... (sequence A175286 in the OEIS)

The Pisano periods of (1,3)-Fibonacci numbers are

1, 3, 1, 6, 24, 3, 24, 6, 3, 24, 120, 6, 156, 24, 24, 12, 16, 3, 90, 24, 24, 120, 22, 6, 120, 156, 9, 24, 28, 24, 240, 24, 120, 48, 24, 6, 171, 90, 156, 24, 336, 24, 42, 120, 24, 66, 736, 12, ... (sequence A175291 in the OEIS)

The Pisano periods of Tribonacci numbers (or 3-step Fibonacci numbers) are

1, 4, 13, 8, 31, 52, 48, 16, 39, 124, 110, 104, 168, 48, 403, 32, 96, 156, 360, 248, 624, 220, 553, 208, 155, 168, 117, 48, 140, 1612, 331, 64, 1430, 96, 1488, 312, 469, 360, 2184, 496, 560, 624, 308, 440, 1209, 2212, 46, 416, ... (sequence A046738 in the OEIS)

The Pisano periods of Tetranacci numbers (or 4-step Fibonacci numbers) are

1, 5, 26, 10, 312, 130, 342, 20, 78, 1560, 120, 130, 84, 1710, 312, 40, 4912, 390, 6858, 1560, 4446, 120, 12166, 260, 1560, 420, 234, 1710, 280, 1560, 61568, 80, 1560, 24560, 17784, 390, 1368, 34290, 1092, 1560, 240, 22230, 162800, 120, 312, 60830, 103822, 520, ... (sequence A106295 in the OEIS)

See also generalizations of Fibonacci numbers.

Pisano periods can be analyzed using algebraic number theory.

Let ${\displaystyle \pi _{k}(n)}$ be the n-th Pisano period of the k-Fibonacci sequence F_k(n) (k can be any natural number, these sequences are defined as F_k(0) = 0, F_k(1) = 1, and for any natural number n > 1, F_k(n) = kF_k(n−1) + F_k(n−2)). If m and n are coprime, then ${\displaystyle \pi _{k}(m\cdot n)=\mathrm {lcm} (\pi _{k}(m),\pi _{k}(n)),}$ by the Chinese remainder theorem: two numbers are congruent modulo mn if and only if they are congruent modulo m and modulo n, assuming these latter are coprime. For example, ${\displaystyle \pi _{1}(3)=8}$ and ${\displaystyle \pi _{1}(4)=6,}$ so ${\displaystyle \pi _{1}(12=3\cdot 4)=\mathrm {lcm} (\pi _{1}(3),\pi _{1}(4))=\mathrm {lcm} (8,6)=24.}$ Thus it suffices to compute Pisano periods for prime powers ${\displaystyle q=p^{n}.}$ (Usually, ${\displaystyle \pi _{k}(p^{n})=p^{n-1}\cdot \pi _{k}(p)}$, unless p is k-Wall-Sun-Sun prime, or k-Fibonacci-Wieferich prime, that is, p² divides F_k(p − 1) or F_k(p + 1), where F_k is the k-Fibonacci sequence, for example, 241 is a 3-Wall-Sun-Sun prime, since 241² divides F₃(242).)

For prime numbers p, these can be analyzed by using Binet's formula:

${\displaystyle F_{k}\left(n\right)={{\varphi _{k}^{n}-(k-\varphi _{k})^{n}} \over {\sqrt {k^{2}+4}}}={{\varphi _{k}^{n}-(-1/\varphi _{k})^{n}} \over {\sqrt {k^{2}+4}}},\,}$ where ${\displaystyle \varphi _{k}}$ is the kth metallic mean

${\displaystyle \varphi _{k}={\frac {k+{\sqrt {k^{2}+4}}}{2}}.}$

If k² + 4 is a quadratic residue modulo p (where p > 2 and p does not divide k² + 4), then ${\displaystyle {\sqrt {k^{2}+4}},1/2,}$ and ${\displaystyle k/{\sqrt {k^{2}+4}}}$ can be expressed as integers modulo p, and thus Binet's formula can be expressed over integers modulo p, and thus the Pisano period divides the totient ${\displaystyle \phi (p)=p-1}$, since any power (such as ${\displaystyle \varphi _{k}^{n}}$) has period dividing ${\displaystyle \phi (p),}$ as this is the order of the group of units modulo p.

For k = 1, this first occurs for p = 11, where 4² = 16 ≡ 5 (mod 11) and 2 · 6 = 12 ≡ 1 (mod 11) and 4 · 3 = 12 ≡ 1 (mod 11) so 4 = √5, 6 = 1/2 and 1/√5 = 3, yielding φ = (1 + 4) · 6 = 30 ≡ 8 (mod 11) and the congruence

${\displaystyle F_{1}\left(n\right)\equiv 3\cdot \left(8^{n}-4^{n}\right){\pmod {11}}.}$

Another example, which shows that the period can properly divide p − 1, is π₁(29) = 14.

If k² + 4 is not a quadratic residue modulo p, then Binet's formula is instead defined over the quadratic extension field (Z/p)[√k² + 4], which has p² elements and whose group of units thus has order p² − 1, and thus the Pisano period divides p² − 1. For example, for p = 3 one has π₁(3) = 8 which equals 3² − 1 = 8; for p = 7, one has π₁(7) = 16, which properly divides 7² − 1 = 48.

This analysis fails for p = 2 and p is a divisor of the squarefree part of k² + 4, since in these cases are zero divisors, so one must be careful in interpreting 1/2 or √k² + 4. For p = 2, k² + 4 is congruent to 1 mod 2 (for k odd), but the Pisano period is not p − 1 = 1, but rather 3 (in fact, this is also 3 for even k). For p divides the squarefree part of k² + 4, the Pisano period is π_k(k² + 4) = p² − p = p(p − 1), which does not divide p − 1 or p² − 1.

One can consider Fibonacci integer sequences and take them modulo n, or put differently, consider Fibonacci sequences in the ring Z/nZ. The period is a divisor of π(n). The number of occurrences of 0 per cycle is 0, 1, 2, or 4. If n is not a prime the cycles include those that are multiples of the cycles for the divisors. For example, for n = 10 the extra cycles include those for n = 2 multiplied by 5, and for n = 5 multiplied by 2.

Table of the extra cycles: (the original Fibonacci cycles are excluded) (using X and E for ten and eleven, respectively)

Number of Fibonacci integer cycles mod n are:

1, 2, 2, 4, 3, 4, 4, 8, 5, 6, 14, 10, 7, 8, 12, 16, 9, 16, 22, 16, 29, 28, 12, 30, 13, 14, 14, 22, 63, 24, 34, 32, 39, 34, 30, 58, 19, 86, 32, 52, 43, 58, 22, 78, 39, 46, 70, 102, ... (sequence A015134 in the OEIS)

• Bloom, D. M. (1965), "Periodicity in generalized Fibonacci sequences", Amer. Math. Monthly, 72 (8): 856–861, doi:10.2307/2315029, JSTOR 2315029, MR 0222015
• 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
• 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
• Falcon, S.; Plaza, A. (2009), "k-Fibonacci sequence modulo m", Chaos, Solitons & Fractals, 41 (1): 497–504, Bibcode:2009CSF....41..497F, doi:10.1016/j.chaos.2008.02.014
• Freyd, Peter; Brown, Kevin S. (1992), "Problems and Solutions: Solutions: E3410", Amer. Math. Monthly, 99 (3): 278–279, doi:10.2307/2325076, JSTOR 2325076
• 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
• Wall, D. D. (1960), "Fibonacci series modulo m", Amer. Math. Monthly, 67 (6): 525–532, doi:10.2307/2309169, JSTOR 2309169
• 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

• The Fibonacci sequence modulo m
• A research for Fibonacci numbers
• Fibonacci sequence starts with q, r modulo m
• Johnson, Robert C., Fibonacci resources
• Fibonacci Mystery - Numberphile on YouTube, a video with Dr. James Grime and the University of Nottingham