View source for Pisano period

{{short description|Period of the Fibonacci sequence modulo an integer}}
[[File:Pisano Periods.png|thumb|300px|right|Plot of the first 10,000 Pisano periods.]]

In [[number theory]], the ''n''th '''Pisano period''', written as ''{{pi}}''(''n''), is the [[periodic function|period]] with which the [[sequence]] of [[Fibonacci number]]s taken [[modular arithmetic|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.<ref name="mathworld">{{MathWorld|urlname=PisanoPeriod|title=Pisano Period}}</ref><ref>[http://matwbn.icm.edu.pl/ksiazki/aa/aa16/aa1621.pdf On Arithmetical functions related to the Fibonacci numbers]. ''Acta Arithmetica'' XVI (1969). Retrieved 22 September 2011.</ref>

== 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, ... {{OEIS|id=A000045}}
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 [[modular arithmetic|modulo]] ''n'' is periodic.
The Pisano period, denoted ''{{pi}}''(''n''), is the length of the period of this sequence. For example, the sequence of Fibonacci numbers [[modular arithmetic|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, ... {{OEIS|id=A082115}}
This sequence has period 8, so ''{{pi}}''(3) = 8.

[[File:PisanoPeriod n3.png|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 ''{{pi}}''(3) = 8.]]

==Properties==
{{MOS|article|[[MOS:BBB]]|date=February 2024}}
=== Parity ===
With the exception of ''{{pi}}''(2)&nbsp;=&nbsp;3, the Pisano period ''{{pi}}''(''n'') is always [[Parity (mathematics)|even]]. 
A proof of this can be given by observing that ''{{pi}}''(''n'') is equal to the order of the [[Fibonacci number#Matrix form|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 matrix|invertible]] 2 by 2 [[Matrix (mathematics)|matrices]] in the [[finite ring]] <math>\mathbb{Z}_n</math>of [[Integers modulo n|integers modulo ''n'']]. Since '''Q''' has determinant −1, the determinant of '''Q'''<sup>''{{pi}}''(''n'')</sup> is (−1)<sup>''{{pi}}''(''n'')</sup>, and since this must equal 1 in <math>\mathbb{Z}_n</math>, either ''n'' ≤ 2 or ''{{pi}}''(''n'') is even.<ref>[http://www.theoremoftheday.org/Binomial/PeriodicFib/TotDPeriodic.pdf A Theorem on Modular Fibonacci Periodicity]. ''Theorem of the Day'' (2015). Retrieved 7 January 2016.</ref>

Since <math>F_0 = 0</math> and <math>F_1 = 1</math> we have that <math>n</math> divides <math>F_{\pi(n)}</math> and <math>(F_{\pi(n)+1} - 1)</math>.

=== Reducing the study to prime numbers ===
If ''m'' and ''n'' are [[coprime]], then ''{{pi}}''(''mn'') is the [[least common multiple]] of ''{{pi}}''(''m'') and ''{{pi}}''(''n''), by the [[Chinese remainder theorem]]. For example, ''{{pi}}''(3) = 8 and ''{{pi}}''(4) = 6 imply ''{{pi}}''(12) = 24.  Thus the study of Pisano periods may be reduced to that of Pisano periods of [[prime power]]s ''q''&thinsp;=&thinsp;''p''<sup>''k''</sup>, for ''k'' ≥ 1.

If ''p'' is [[Prime number|prime]], ''{{pi}}''(''p''<sup>''k''</sup>) divides ''p''<sup>''k''–1</sup>&thinsp;''{{pi}}''(''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).

=== Study of prime numbers ===
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 [[Parity (mathematics)|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''&thinsp;=&thinsp;2<sup>''k''</sup>, then ''{{pi}}''(''n'') = 3·2<sup>''k''–1</sup> = {{sfrac|3·2<sup>''k''</sup>|2}} = {{sfrac|3''n''|2}}.
* if ''n''&thinsp;=&thinsp;5<sup>''k''</sup>, then ''{{pi}}''(''n'') = 20·5<sup>''k''–1</sup> = {{sfrac|20·5<sup>''k''</sup>|5}} = 4''n''.

From these it follows that if ''n'' = 2{{space|hair}}·{{space|hair}}5<sup>''k''</sup> then  ''{{pi}}''(''n'') = 6''n''.

[[File:PisanoPeriod n5.png|thumb|State space visualization of the Pisano period for n = 5]]

[[File:PisanoPeriod n10.png|thumb|State space visualization of the Pisano period for n = 10]]

The remaining primes all lie in the residue classes <math>p \equiv \pm 1 \pmod {10}</math> or <math>p \equiv \pm 3 \pmod {10}</math>. If ''p'' is a prime different from 2 and 5, then the modulo ''p'' analogue of [[Binet's formula]] implies that ''{{pi}}''(''p'') is the [[multiplicative order]] of a [[Zero of a function|root]] of {{math|''x''<sup>2</sup> − ''x'' − 1}} modulo ''p''. 

If <math>p \equiv \pm 1 \pmod {10}</math>, these roots belong to <math>\mathbb{F}_{p} = \mathbb{Z}/p\mathbb{Z}</math> (by [[quadratic reciprocity]]). Thus their order, ''{{pi}}''(''p'') is a [[divisor]] of ''p'' − 1. For example, ''{{pi}}''(11) = 11 − 1 = 10 and ''{{pi}}''(29) = (29 − 1)/2 = 14.

If <math>p \equiv \pm 3 \pmod {10},</math> the roots modulo ''p'' of {{math|''x''<sup>2</sup> − ''x'' − 1}} 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>&thinsp;''p''</sup> = ''s'', and thus ''r''<sup>&thinsp;''p''+1</sup> = –1. That is ''r''<sup>&thinsp;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. This quotient is always a multiple of 4. The first examples of such a ''p'', for which ''{{pi}}''(''p'') is smaller than 2(''p''+1), are ''{{pi}}''(47) = 2(47&thinsp;+&thinsp;1)/3 = 32, ''{{pi}}''(107) = 2(107&thinsp;+&thinsp;1)/3 = 72 and  ''{{pi}}''(113) = 2(113&thinsp;+&thinsp;1)/3 = 76. ([[#Tables|See the table below]])

It follows from above results, that if ''n'' = ''p''<sup>''k''</sup> is an odd prime power such that ''{{pi}}''(''n'') > ''n'', then ''{{pi}}''(''n'')/4 is an integer that is not greater than ''n''. The multiplicative property of Pisano periods imply thus that
:''{{pi}}''(''n'') &le; 6''n'', with equality if and only if ''n'' = 2&thinsp;·&thinsp;5<sup>''r''</sup>, for ''r'' ≥ 1.<ref>{{harvtxt|Freyd|Brown|1992}}</ref>

The first examples are ''{{pi}}''(10) = 60 and ''{{pi}}''(50) = 300. If ''n'' is not of the form 2&thinsp;·&thinsp;5<sup>''r''</sup>, then ''{{pi}}''(''n'') &le; 4''n''.

== Tables ==
The first twelve Pisano periods {{OEIS|id=A001175}} and their cycles (with spaces before the zeros for readability) are<ref>[https://oeis.org/A001175/a001175.jpg Graph of the cycles modulo 1 to 24. Each row of the image represents a different modulo base ''n'', from 1 at the bottom to 24 at the top. The columns represent the Fibonacci numbers mod ''n'', from ''F''(0) mod ''n'' at the left to ''F''(59) mod ''n'' on the right. In each cell, the brightness indicates the value of the residual, from dark for 0 to near-white for ''n''−1.  Blue squares on the left represent the first period; the number of blue squares is the Pisano number.]</ref> (using X and E for ten and eleven, respectively):

{|class="wikitable"
!''n''!!π(''n'')!!number of zeros in the cycle ({{oeis|id=A001176}})!!cycle ({{oeis|id=A161553}})!![[OEIS]] sequence for the cycle
|-
|1||[[1 (number)|1]]||1||0||{{OEIS link|id=A000004}}
|-
|2||[[3 (number)|3]]||1||011||{{OEIS link|id=A011655}}
|-
|3||[[8 (number)|8]]||2||0112 0221||{{OEIS link|id=A082115}}
|-
|4||[[6 (number)|6]]||1||011231||{{OEIS link|id=A079343}}
|-
|5||[[20 (number)|20]]||4||01123 03314 04432 02241||{{OEIS link|id=A082116}}
|-
|6||[[24 (number)|24]]||2||011235213415 055431453251||{{OEIS link|id=A082117}}
|-
|7||[[16 (number)|16]]||2||01123516 06654261||{{OEIS link|id=A105870}}
|-
|8||[[12 (number)|12]]||2||011235 055271||{{OEIS link|id=A079344}}
|-
|9||[[24 (number)|24]]||2||011235843718 088764156281||{{OEIS link|id=A007887}}
|-
|10||[[60 (number)|60]]||4||011235831459437 077415617853819 099875279651673 033695493257291||{{OEIS link|id=A003893}}
|-
|11||[[10 (number)|10]]||1||01123582X1||{{OEIS link|id=A105955}}
|-
|12||[[24 (number)|24]]||2||011235819X75 055X314592E1||{{OEIS link|id=A089911}}
|}

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''(2''k'') (''k'' ≥ 2), then π(''n'') = 4''k''; if ''n'' = ''F''(2''k''&thinsp;+&thinsp;1) (''k'' ≥ 2), then π(''n'') = 8''k''&thinsp;+&thinsp;4. That is, if the modulo base is a Fibonacci number (≥&thinsp;3) with an even index, the period is twice the index and the cycle has two zeros. If the base is a Fibonacci number (≥&thinsp;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''(2''k'') (''k'' ≥ 1), then π(''n'') = 8''k''; if ''n'' = ''L''(2''k''&thinsp;+&thinsp;1) (''k'' ≥ 1), then π(''n'') = 4''k''&thinsp;+&thinsp;2. That is, if the modulo base is a Lucas number (≥&thinsp;3) with an even index, the period is four times the index. If the base is a Lucas number (≥&thinsp;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''(2''m''&nbsp;+&nbsp;1) and ''n''&nbsp;&minus;&nbsp;''F''(2''m''), with ''m'' decreasing.

==Number of zeros in the cycle==
{{Refimprove section|date=August 2018}}

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''&nbsp;=&nbsp;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>&nbsp;≡&nbsp;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, ... {{OEIS|id=A001177}}

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>.<ref name=renault>{{Cite web|url=http://webspace.ship.edu/msrenault/fibonacci/fib.htm|title=The Fibonacci Sequence Modulo M, by Marc Renault|website=webspace.ship.edu|access-date=2018-08-22}}</ref>

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>.<ref name=renault />

== Generalizations ==
The '''Pisano periods''' of [[Lucas number]]s 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, ... {{OEIS|id=A106291 }}

The '''Pisano periods''' of [[Pell number]]s (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, ... {{OEIS|id=A175181}}

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, ... {{OEIS|id=A175182}}

The '''Pisano periods''' of [[Jacobsthal number]]s (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, ... {{OEIS|id=A175286}}

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, ... {{OEIS|id=A175291}}

The '''Pisano periods''' of [[Tribonacci number]]s (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, ... {{OEIS|id=A046738}}

The '''Pisano periods''' of [[Tetranacci number]]s (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, ... {{OEIS|id=A106295}}

See also [[generalizations of Fibonacci numbers]].

== Number theory ==
Pisano periods can be analyzed using [[algebraic number theory]].

Let <math>\pi_k(n)</math> be the ''n''-th Pisano period of the ''k''-Fibonacci sequence ''F''<sub>''k''</sub>(''n'') (''k'' can be any [[natural number]], these sequences are defined as ''F''<sub>''k''</sub>(0) = 0, ''F''<sub>''k''</sub>(1) = 1, and for any natural number ''n'' > 1, ''F''<sub>''k''</sub>(''n'') = ''kF''<sub>''k''</sub>(''n''−1) + ''F''<sub>''k''</sub>(''n''−2)). If ''m'' and ''n'' are [[coprime]], then <math>\pi_k(m\cdot n) = \mathrm{lcm}(\pi_k(m),\pi_k(n))</math>, 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, <math>\pi_1(3)=8</math> and <math>\pi_1(4)=6,</math> so <math>\pi_1(12=3\cdot 4) = \mathrm{lcm}(\pi_1(3),\pi_1(4))= \mathrm{lcm}(8,6)=24.</math> Thus it suffices to compute Pisano periods for [[prime power]]s <math>q=p^n.</math> (Usually, <math>\pi_k(p^n) = p^{n-1}\cdot \pi_k(p)</math>, unless ''p'' is ''k''-[[Wall–Sun–Sun prime]], or ''k''-Fibonacci–Wieferich prime, that is, ''p''<sup>2</sup> divides ''F''<sub>''k''</sub>(''p''&thinsp;−&thinsp;1) or ''F''<sub>''k''</sub>(''p''&thinsp;+&thinsp;1), where ''F''<sub>''k''</sub> is the ''k''-Fibonacci sequence, for example, 241 is a 3-Wall–Sun–Sun prime, since 241<sup>2</sup> divides ''F''<sub>3</sub>(242).)

For prime numbers ''p'', these can be analyzed by using [[Binet's formula]]:
:<math>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}}},\,</math> where <math>\varphi_k</math> is the ''k''th [[metallic mean]]
:<math>\varphi_k = \frac{k + \sqrt{k^2+4}}{2}.</math>

If ''k''<sup>2</sup>&thinsp;+&thinsp;4 is a [[quadratic residue]] modulo ''p'' (where ''p'' > 2 and ''p'' does not divide ''k''<sup>2</sup>&thinsp;+&thinsp;4), then <math>\sqrt{k^2+4}, 1/2,</math> and <math>k/\sqrt{k^2+4}</math> 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]] <math>\phi(p)=p-1</math>, since any power (such as <math>\varphi_k^n</math>) has period dividing <math>\phi(p),</math> as this is the [[Order (group theory)|order]] of the [[group of units]] modulo ''p''.

For ''k'' = 1, this first occurs for ''p'' = 11, where 4<sup>2</sup>&nbsp;=&nbsp;16 ≡ 5&nbsp;(mod&nbsp;11) and 2&thinsp;·&thinsp;6 = 12 ≡ 1&nbsp;(mod&nbsp;11) and 4&thinsp;·&thinsp;3 = 12 ≡ 1&nbsp;(mod&nbsp;11) so 4&nbsp;=&nbsp;{{radic|5}}, 6 = 1/2 and 1/{{radic|5}}&nbsp;=&nbsp;3, yielding ''&phi;'' = (1&thinsp;+&thinsp;4)&thinsp;·&thinsp;6 =&nbsp;30 ≡ 8&nbsp;(mod&nbsp;11) and the congruence

:<math>F_1\left(n\right) \equiv 3\cdot \left(8^n - 4^n\right) \pmod{11}.</math>

Another example, which shows that the period can properly divide ''p''&nbsp;−&nbsp;1, is ''&pi;''<sub>1</sub>(29) = 14.

If ''k''<sup>2</sup>&thinsp;+&thinsp;4 is not a quadratic residue modulo ''p'', then Binet's formula is instead defined over the [[quadratic extension]] field <math>(\mathbb{Z}/p)[\sqrt{k^2+4}]</math>, which has ''p''<sup>2</sup> elements and whose group of units thus has order ''p''<sup>2</sup>&nbsp;&minus;&nbsp;1, and thus the Pisano period divides ''p''<sup>2</sup>&nbsp;&minus;&nbsp;1.  For example, for ''p''&nbsp;=&nbsp;3 one has ''&pi;''<sub>1</sub>(3)&nbsp;=&nbsp;8 which equals 3<sup>2</sup>&nbsp;&minus;&nbsp;1&nbsp;=&nbsp;8; for ''p''&nbsp;=&nbsp;7, one has ''&pi;''<sub>1</sub>(7)&nbsp;=&nbsp;16, which properly divides 7<sup>2</sup>&nbsp;&minus;&nbsp;1&nbsp;=&nbsp;48.

This analysis fails for ''p'' = 2 and ''p'' is a divisor of the squarefree part of ''k''<sup>2</sup>&thinsp;+&thinsp;4, since in these cases are [[zero divisor]]s, so one must be careful in interpreting 1/2 or&nbsp;<math>\sqrt{k^2+4}</math>.  For ''p'' = 2, {{nowrap|''k''<sup>2</sup>&thinsp;+&thinsp;4}} is congruent to 1 mod&nbsp;2 (for ''k'' odd), but the Pisano period is not ''p''&thinsp;−&thinsp;1 = 1, but rather&nbsp;3 (in fact, this is also 3 for even ''k''). For ''p'' divides the squarefree part of ''k''<sup>2</sup>&thinsp;+&thinsp;4, the Pisano period is ''&pi;''<sub>''k''</sub>(''k''<sup>2</sup>&thinsp;+&thinsp;4) = ''p''<sup>2</sup>&thinsp;−&thinsp;''p'' = ''p''(''p''&thinsp;−&thinsp;1), which does not divide ''p''&thinsp;−&thinsp;1 or ''p''<sup>2</sup>&thinsp;−&thinsp;1.

==Fibonacci integer sequences modulo ''n''==
One can consider [[Generalizations of Fibonacci numbers#Fibonacci integer sequences|Fibonacci integer sequences]] and take them modulo ''n'', or put differently, consider [[Generalizations of Fibonacci numbers#Vector space|Fibonacci sequences]] in the ring [[cyclic group|'''Z'''/''n'''''Z''']]. 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)

{|class="wikitable"
!''n''!!multiples!!other cycles!!number of cycles<br>(including the original Fibonacci cycles)
|-
|1||||||1
|-
|2||0||||2
|-
|3||0||||2
|-
|4||0, 022||033213||4
|-
|5||0||1342||3
|-
|6||0, 0224 0442, 033||||4
|-
|7||0||02246325 05531452, 03362134 04415643||4
|-
|8||0, 022462, 044, 066426||033617 077653, 134732574372, 145167541563||8
|-
|9||0, 0336 0663||022461786527 077538213472, 044832573145 055167426854||5
|-
|10||0, 02246 06628 08864 04482, 055, 2684||134718976392||6
|-
|11||0||02246X5492, 0336942683, 044819X874, 055X437X65, 0661784156, 0773X21347, 0885279538, 0997516729, 0XX986391X, 14593, 18964X3257, 28X76||14
|-
|12||0, 02246X42682X 0XX8628X64X2, 033693, 0448 0884, 066, 099639||07729E873X1E 0EEX974E3257, 1347E65E437X538E761783E2, 156E5491XE98516718952794||10
|}

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, ... {{OEIS|id=A015134}}

==Notes==
{{reflist|2}}

==References==
<!-- alphabetical order -->
*{{Citation
|first1=D. M.
|last1=Bloom
|title=Periodicity in generalized Fibonacci sequences
|journal=Amer. Math. Monthly
|year=1965
|volume=72
|issue=8
|pages=856–861
|jstor = 2315029
|mr=0222015
|doi=10.2307/2315029
}}
*{{Citation
|first1=Richard P.
|last1=Brent
|author1-link=Richard Brent (scientist)
|title=On the periods of generalized Fibonacci sequences
|journal=Mathematics of Computation
|volume=63
|issue=207
|pages=389–401
|bibcode=1994MaCom..63..389B
|year=1994
|jstor = 2153583
|mr=1216256
|arxiv = 1004.5439
|doi=10.2307/2153583|s2cid=1038296
}}
*{{Citation
|first1=H. T.
|last1=Engstrom
|title=On sequences defined by linear recurrence relations
|journal=Trans. Am. Math. Soc.
|volume=33
|issue=1
|pages=210–218
|year=1931
|doi=10.1090/S0002-9947-1931-1501585-5
|jstor = 1989467
|mr=1501585
|doi-access=free
}}
*{{Citation
|first1=S.
|last1=Falcon
|first2=A.
|last2=Plaza
|title=''k''-Fibonacci sequence modulo ''m''
|journal=Chaos, Solitons & Fractals
|volume=41
|issue=1
|year=2009
|pages=497–504
|doi=10.1016/j.chaos.2008.02.014|bibcode=2009CSF....41..497F
}}
*{{Citation
|first1=Peter
|last1=Freyd
|first2=Kevin S.
|last2=Brown
|title=Problems and Solutions: Solutions: E3410
|journal=Amer. Math. Monthly
|volume=99
|issue=3
|pages=278–279
|year=1992
|doi=10.2307/2325076
|jstor=2325076
}}
*{{Citation
|first1=R. R.
|last1=Laxton
|title=On groups of linear recurrences
|journal=[[Duke Mathematical Journal]]
|volume=36
|issue=4
|doi=10.1215/S0012-7094-69-03687-4
|pages=721–736
|year=1969
|mr = 0258781
}}
* {{Citation
|first1= D. D.
|last1=Wall
|title=Fibonacci series modulo m
|journal=Amer. Math. Monthly
|year=1960
|pages=525–532
|volume=67
|issue=6
| jstor = 2309169
|doi=10.2307/2309169
}}
*{{Citation
|first1=Morgan
|last1=Ward | author1-link = Morgan Ward
|title=The characteristic number of a sequence of integers satisfying a linear recursion relation
|journal=Trans. Am. Math. Soc.
|volume=33
|issue=1
|pages=153–165
|doi=10.1090/S0002-9947-1931-1501582-X
|year=1931
|jstor = 1989464
|doi-access=free
}}
*{{Citation
|first1=Morgan
|last1=Ward
|title=The arithmetical theory of linear recurring series
|journal=Trans. Am. Math. Soc.
|volume=35
|issue=3
|doi=10.1090/S0002-9947-1933-1501705-4
|pages=600–628
|year=1933
|jstor = 1989851
|doi-access=free
}}
*{{Citation
|first1=Neal
|last1=Zierler
|title=Linear recurring sequences
|journal=J. SIAM
|volume=7
|issue=1
|pages=31–38
|doi=10.1137/0107003
|year=1959
|jstor = 2099002
|mr=0101979
}}

==External links==
*[http://webspace.ship.edu/msrenault/fibonacci/fib.htm The Fibonacci sequence modulo m]
*[http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibmaths.html#section6 A research for Fibonacci numbers]
*[http://webbox.lafayette.edu/~reiterc/nt/qr_fib_ec_preprint.pdf Fibonacci sequence starts with q, r modulo m]
*{{Citation
|first1=Robert C.
|last1=Johnson
|url=http://www.dur.ac.uk/bob.johnson/fibonacci/
|title= Fibonacci resources
}}
*{{YouTube|Nu-lW-Ifyec|Fibonacci Mystery - Numberphile}}, a video with Dr. James Grime and the [[University of Nottingham]]

[[Category:Fibonacci numbers]]
[[Category:Modular arithmetic]]