Register to reply 
Pisano Periods  Fibonacci Numbers mod p 
Share this thread: 
#1
Feb313, 08:40 PM

PF Gold
P: 3

Let F_{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. Let p = a prime such that p[itex]\equiv[/itex]{2,3}mod 5 so that h(p)[itex]\mid[/itex] 2 p + 2. Let h(p) denote of the length of the Pisano period. If D = {d_{1},d_{2},d_{3}[itex]\cdots[/itex]d_{k}} is the nonempty set of k divisors of 2 p + 2 Then: h(p) = min[d_{i}] such that F_{d(i + 1)}[itex]\equiv[/itex] 1 mod p and
Now let p = a prime such that p[itex]\equiv[/itex]{1,4}mod 5 so that h(p)[itex]\mid[/itex] p  1. If p has a primitive root such that g^{2}[itex]\equiv[/itex] g + 1 mod(p) then h(p) = p  1. Note that g^{2}[itex]\equiv[/itex] g + 1 mod(p) has two roots: 1.618033988 and 0.618033988  variants of the Golden Ratio. If p has no primitive root then D = {d_{1},d_{2},d_{3}[itex]\cdots[/itex]d_{k}} is the nonempty set of k divisors of p  1. Let h(p) = min[d_{i}] such that F_{d(i + 1)}[itex]\equiv[/itex] 1 mod p and d_{i} ~[itex]\mid[/itex] p + 1 and d_{i} ~[itex]\mid[/itex] floor [ p/2]]. If m is any positive integer > 3 we can write F_{n} mod F_{m} where h(F_{m}) is given by



#2
Feb1013, 09:47 AM

P: 894




#3
Feb1013, 10:00 AM

PF Gold
P: 3

Thanks.
No, I was trying to find  does not divide  but couldn't so I sort of made that up. But perhaps I should clarify it, because it is not the standard notation. 


#4
Feb1013, 06:49 PM

P: 894

Pisano Periods  Fibonacci Numbers mod p



#5
Feb1113, 05:57 AM

PF Gold
P: 3

Good catch. I will add some more observations on this topic as time permits. 


#6
Feb1213, 10:14 AM

P: 894




Register to reply 
Related Discussions  
Representing numbers as sums of fibonacci numbers  Programming & Computer Science  4  
Lucas Numbers/ Fibonacci Numbers Proof  Calculus & Beyond Homework  3  
Where Fibonacci numbers surpass prime numbers  Linear & Abstract Algebra  4  
Fibonacci numbers  Introductory Physics Homework  1 