Let F(adsbygoogle = window.adsbygoogle || []).push({}); _{n}be the n^{th}number of a Fibonacci sequence.

We know that F_{n}mod(p) forms a periodic sequence (http://en.wikipedia.org/wiki/Pisano_period) called the Pisano Period.

Letp= a prime such thatp[itex]\equiv[/itex]{2,3}mod 5 so thath(p)[itex]\mid[/itex] 2p+ 2.

Leth(p) denote of the length of the Pisano period.

IfD= {d,_{1}d,_{2}d[itex]\cdots[/itex]_{3}d} is the non-empty set of_{k}kdivisors of 2p+ 2

Then:

h(p) = min[d] such that F_{i}_{d(i + 1)}[itex]\equiv[/itex] 1 modp

and

d~[itex]\mid[/itex][itex]\frac{1}{2}[/itex]_{i}p(p+ 1)d~[itex]\mid[/itex]_{i}p+ 1d~[itex]\mid[/itex] 3 (_{i}p- 1)

Now letp= a prime such thatp[itex]\equiv[/itex]{1,4}mod 5 so thath(p)[itex]\mid[/itex]p- 1.

Ifphas a primitive root such thatg[itex]\equiv[/itex]^{2}g+ 1 mod(p) thenh(p) =p- 1.

Note thatg[itex]\equiv[/itex]^{2}g+ 1 mod(p) has two roots: 1.618033988 and -0.618033988 - variants of theGolden Ratio.

Ifphas no primitive root thenD= {d,_{1}d,_{2}d[itex]\cdots[/itex]_{3}d} is the non-empty set of_{k}kdivisors ofp- 1.

Leth(p) = min[d] such that F_{i}_{d(i + 1)}[itex]\equiv[/itex] 1 modp

and

d~[itex]\mid[/itex]_{i}p+ 1 andd~[itex]\mid[/itex]_{i}floor[p/2]].

Ifmis any positive integer > 3 we can write Fmod F_{n}where_{m}h(F) is given by_{m}

h(F) = 2_{m}m↔mis evenh(F) = 4_{m}m↔mis odd

**Physics Forums | Science Articles, Homework Help, Discussion**

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Pisano Periods - Fibonacci Numbers mod p

**Physics Forums | Science Articles, Homework Help, Discussion**