Pisano period


In number theory, the nth Pisano period, written , 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:
defined by the recurrence relation
For any integer n, the sequence of Fibonacci numbers Fi taken modulo n is periodic.
The Pisano period, denoted ', is the length of the period of this sequence. For example, the sequence of Fibonacci numbers modulo 3 begins:
This sequence has period 8, so ' = 8.

Properties

With the exception of ' = 3, the Pisano period ' is always even.
A simple proof of this can be given by observing that ' is equal to the order of the Fibonacci matrix.
in the general linear group GL2 of invertible 2 by 2 matrices in the finite ring ℤn of integers modulo n. Since Q has determinant −1, the determinant of Q' is ', and since this must equal 1 in ℤn, either n ≤ 2 or ' is even.
If m and n are coprime, then ' is the least common multiple of ' and ', by the Chinese remainder theorem. For example, ' = 8 and ' = 6 imply ' = 24. Thus the study of Pisano periods may be reduced to that of Pisano periods of prime powers q = pk, for k ≥ 1.
If p is prime, ' divides pk–1 '. It is conjectured that
for every prime p and integer k > 1. Any prime p providing a counterexample would necessarily be a Wall-Sun-Sun prime, and such primes are also conjectured not to exist.
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:
From these it follows that if n = 2·5k then ' = 6n.
The remaining primes all lie in the residue classes or. If p is a prime different from 2 and 5, then the modulo p analogue of Binet's formula implies that ' is the multiplicative order of the roots of modulo p. If, these roots belong to . Thus their order, ' is a divisor of p − 1. For example, ' = 11 − 1 = 10 and ' = /2 = 14.
If the roots modulo p of do not belong to , and belong to the finite field
As the Frobenius automorphism 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 = 1, and the Pisano period, which is the order of r, is the quotient of 2 by an odd divisor. This quotient is always a multiple of 4. The first examples of such a p, for which ' is smaller than 2, are ' = 2/3 = 32, ' = 2/3 = 72 and ' = 2/3 = 76.
It follows from above results, that if n = pk is an odd prime power such that ' > n, then '/4 is an integer that is not greater than n. The multiplicative property of Pisano periods imply thus that
The first examples are ' = 60 and ' = 300. If n is not of the form 2 · 5r, then ' ≤ 4n.

Tables

The first twelve Pisano periods and their cycles are:
nπnumber of zeros in the cycle cycle OEIS sequence for the cycle
1110
231011
3820112 0221
461011231
520401123 03314 04432 02241
6242011235213415 055431453251
716201123516 06654261
8122011235 055271
9242011235843718 088764156281
10604011235831459437 077415617853819 099875279651673 033695493257291
1110101123582A1
12242011235819A75 055A314592B1

The first 144 Pisano periods are shown in the following table:
π+1+2+3+4+5+6+7+8+9+10+11+12
0+13862024161224601024
12+284840243624186016304824
24+10084724814120304840368024
36+7618566040488830120483224
48+1123007284108722048724258120
60+6030489614012013636482407024
72+14822820018801687812021612016848
84+180264566044120112481209618048
96+196336120300507220884801087272
108+1086015248767224042168174144120
120+1106040305004825619288420130120
132+1444083603627648462403221014024

Pisano periods of Fibonacci numbers

If n = F, then π = 4k; if n = F, then π = 8k + 4. That is, if the modulo base is a Fibonacci number with an even index, the period is twice the index and the cycle has 2 zeros. If the base is a Fibonacci number with an odd index, the period is 4 times the index and the cycle has 4 zeros.
kFπfirst half of cycle or first quarter of cycle or all cycle
1110
2110
3230, 1, 1
4380, 1, 1, 2,
55200, 1, 1, 2, 3,
68120, 1, 1, 2, 3, 5,
713280, 1, 1, 2, 3, 5, 8,
821160, 1, 1, 2, 3, 5, 8, 13,
934360, 1, 1, 2, 3, 5, 8, 13, 21,
1055200, 1, 1, 2, 3, 5, 8, 13, 21, 34,
1189440, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55,
12144240, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89,
13233520, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144
14377280, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233
15610600, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377
16987320, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610
171597680, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987
182584360, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597
194181760, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584
206765400, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181
2110946840, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765
2217711440, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946
2328657920, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711
2446368480, 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, then π = 8k; if n = L, then π = 4k + 2. That is, if the modulo base is a Lucas number with an even index, the period is 4 times the index. If the base is a Lucas number with an odd index, the period is twice the index.
kLπfirst half of cycle or first quarter of cycle or all cycle
1110
2380, 1,
3460, 1, 1,
47160, 1, 1, 2,
511100, 1, 1, 2, 3,
618240, 1, 1, 2, 3, 5,
729140, 1, 1, 2, 3, 5, 8,
847320, 1, 1, 2, 3, 5, 8, 13,
976180, 1, 1, 2, 3, 5, 8, 13, 21,
10123400, 1, 1, 2, 3, 5, 8, 13, 21, 34,
11199220, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55,
12322480, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89,
13521260, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144
14843560, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233
151364300, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377
162207640, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610
173571340, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987
185778720, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597
199349380, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584
2015127800, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181
2124476420, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765
2239603880, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946
2364079460, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711
24103682960, 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 2 zeros. For odd k, the cycle has only 1 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 and n − F, 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.
For generalized Fibonacci sequences 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. They are:
In Renault's paper the number of zeros is called the "order" of F mod m, denoted, and the "rank of apparition" is called the "rank" and denoted.
According to Wall's conjecture,. If has prime factorization then.

Generalizations

The Pisano periods of Pell numbers are
The Pisano periods of 3-Fibonacci numbers are
The Pisano periods of Jacobsthal numbers are
The Pisano periods of -Fibonacci numbers are
The Pisano periods of Tribonacci numbers are
The Pisano periods of Tetranacci numbers are
See also generalizations of Fibonacci numbers.

Number theory

Pisano periods can be analyzed using algebraic number theory.
Let be the n-th Pisano period of the k-Fibonacci sequence Fk = 0, Fk = 1, and for any natural number n > 1, Fk = kFk + Fk). If m and n are coprime, then 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, and so Thus it suffices to compute Pisano periods for prime powers or Fk, where Fk is the k-Fibonacci sequence, for example, 241 is a 3-Wall-Sun-Sun prime, since 2412 divides F3
For prime numbers p, these can be analyzed by using Binet's formula:
If k2 + 4 is a quadratic residue modulo p, then and 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, since any power has period dividing as this is the order of the group of units modulo p.
For k = 1, this first occurs for p = 11, where 42 = 16 ≡ 5 and 2 · 6 = 12 ≡ 1 and 4 · 3 = 12 ≡ 1 so 4 = , 6 = 1/2 and 1/ = 3, yielding φ =  · 6 = 30 ≡ 8 and the congruence
Another example, which shows that the period can properly divide p − 1, is π1 = 14.
If k2 + 4 is not a quadratic residue modulo p, then Binet's formula is instead defined over the quadratic extension field , which has p2 elements and whose group of units thus has order p2 − 1, and thus the Pisano period divides p2 − 1. For example, for p = 3 one has π1 = 8 which equals 32 − 1 = 8; for p = 7, one has π1 = 16, which properly divides 72 − 1 = 48.
This analysis fails for p = 2 and p is a divisor of the squarefree part of k2 + 4, since in these cases are zero divisors, so one must be careful in interpreting 1/2 or . For p = 2, is congruent to 1 mod 2, but the Pisano period is not p − 1 = 1, but rather 3. For p divides the squarefree part of k2 + 4, the Pisano period is πk = p2 − p = p, which does not divide p − 1 or p2 − 1.

Fibonacci integer sequences modulo ''n''

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 π. 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:
nmultiplesother cyclesnumber of cycles
11
202
302
40, 0220332134
5013423
60, 0224 0442, 0334
7002246325 05531452, 03362134 044156434
80, 022462, 044, 066426033617 077653, 134732574372, 1451675415638
90, 0336 0663022461786527 077538213472, 044832573145 0551674268545
100, 02246 06628 08864 04482, 055, 26841347189763926
11002246X5492, 0336942683, 044819X874, 055X437X65, 0661784156, 0773X21347, 0885279538, 0997516729, 0XX986391X, 14593, 18964X3257, 28X7614
120, 02246X42682X 0XX8628X64X2, 033693, 0448 0884, 066, 09963907729E873X1E 0EEX974E3257, 1347E65E437X538E761783E2, 156E5491XE9851671895279410

Number of Fibonacci integer cycles mod n are: