Register to reply

Pisano Periods - Fibonacci Numbers mod p

by LDP
Tags: fibonacci, numbers, periods, pisano
Share this thread:
LDP
#1
Feb3-13, 08:40 PM
PF Gold
LDP's Avatar
P: 3
Let Fn be the nth number of a Fibonacci sequence.
We know that Fnmod(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 = {d1,d2,d3[itex]\cdots[/itex]dk} is the non-empty set of k divisors of 2 p + 2
Then:
h(p) = min[di] such that Fd(i + 1)[itex]\equiv[/itex] 1 mod p
and
  1. di ~[itex]\mid[/itex][itex]\frac{1}{2}[/itex] p (p + 1)
  2. di ~[itex]\mid[/itex] p + 1
  3. di ~[itex]\mid[/itex] 3 (p - 1)

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 g2[itex]\equiv[/itex] g + 1 mod(p) then h(p) = p - 1.
Note that g2[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 = {d1,d2,d3[itex]\cdots[/itex]dk} is the non-empty set of k divisors of p - 1.
Let h(p) = min[di] such that Fd(i + 1)[itex]\equiv[/itex] 1 mod p
and
di ~[itex]\mid[/itex] p + 1 and di ~[itex]\mid[/itex] floor [ p/2]].

If m is any positive integer > 3 we can write Fn mod Fm where h(Fm) is given by
  1. h(Fm) = 2mm is even
  2. h(Fm) = 4mm is odd
Phys.Org News Partner Science news on Phys.org
Law changed to allow 'unlocking' cellphones
Microsoft sues Samsung alleging contract breach
Best evidence yet for coronal heating theory detected by NASA sounding rocket
ramsey2879
#2
Feb10-13, 09:47 AM
P: 894
Quote Quote by LDP View Post
Let Fn be the nth number of a Fibonacci sequence.
We know that Fnmod(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 = {d1,d2,d3[itex]\cdots[/itex]dk} is the non-empty set of k divisors of 2 p + 2
Then:
h(p) = min[di] such that Fd(i + 1)[itex]\equiv[/itex] 1 mod p
and
  1. di ~[itex]\mid[/itex][itex]\frac{1}{2}[/itex] p (p + 1)
  2. di ~[itex]\mid[/itex] p + 1
  3. di ~[itex]\mid[/itex] 3 (p - 1)

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 g2[itex]\equiv[/itex] g + 1 mod(p) then h(p) = p - 1.
Note that g2[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 = {d1,d2,d3[itex]\cdots[/itex]dk} is the non-empty set of k divisors of p - 1.
Let h(p) = min[di] such that Fd(i + 1)[itex]\equiv[/itex] 1 mod p
and
di ~[itex]\mid[/itex] p + 1 and di ~[itex]\mid[/itex] floor [ p/2]].

If m is any positive integer > 3 we can write Fn mod Fm where h(Fm) is given by
  1. h(Fm) = 2mm is even
  2. h(Fm) = 4mm is odd
Interesting to say the least. I am curious as to what is meant by
  1. di ~[itex]\mid[/itex][itex]\frac{1}{2}[/itex] p (p + 1)
  2. di ~[itex]\mid[/itex] p + 1
  3. di ~[itex]\mid[/itex] 3 (p - 1)
I think you are saying di approximately divides the expressions on the right, but I dont know what that means. Can you give an example?
LDP
#3
Feb10-13, 10:00 AM
PF Gold
LDP's Avatar
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.

ramsey2879
#4
Feb10-13, 06:49 PM
P: 894
Pisano Periods - Fibonacci Numbers mod p

Quote Quote by LDP View Post
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.
Clarification noted. Only problem that I see is for p = 2 (for which you say h(p) = 2p + 2 = 6). Since h(2) = 3, I guess you meant odd primes that = 2,3, mod 5 (whose last digit is either a 3 or 7). PS, I noted that for the composites ending in 3 or 7 which I checked, that h(p) <> 2p + 2. Could this be a test for primes ending in 3 or 7?
LDP
#5
Feb11-13, 05:57 AM
PF Gold
LDP's Avatar
P: 3
Quote Quote by ramsey2879 View Post
Clarification noted. Only problem that I see is for p = 2 (for which you say h(p) = 2p + 2 = 6). Since h(2) = 3, I guess you meant odd primes that = 2,3, mod 5 (whose last digit is either a 3 or 7). PS, I noted that for the composites ending in 3 or 7 which I checked, that h(p) <> 2p + 2. Could this be a test for primes ending in 3 or 7?
Indeed, I should have said "only odd primes".
Good catch.
I will add some more observations on this topic as time permits.
ramsey2879
#6
Feb12-13, 10:14 AM
P: 894
Quote Quote by ramsey2879 View Post
Clarification noted. Only problem that I see is for p = 2 (for which you say h(p) = 2p + 2 = 6). Since h(2) = 3, I guess you meant odd primes that = 2,3, mod 5 (whose last digit is either a 3 or 7). PS, I noted that for the composites ending in 3 or 7 which I checked, that h(p) <> 2p + 2. Could this be a test for primes ending in 3 or 7?
I checked and found that the following composites ending in 7 have Pisano periods that divide 2p + 2 and do not divide (1/2)*p(p+1) or p+1 or 3p-3. (All primes ending in 7 less than 100,000 meet this test also). The composites ending in 7 and less than 100,000 meeting the test are 377, 3827, 5777, 10877, 25877, 60377, 75077 and 90287.


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