Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Pisano Periods - Fibonacci Numbers mod p

  1. Feb 3, 2013 #1

    LDP

    User Avatar
    Gold Member

    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
     
    Last edited: Feb 4, 2013
  2. jcsd
  3. Feb 10, 2013 #2
    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?
     
  4. Feb 10, 2013 #3

    LDP

    User Avatar
    Gold Member

    :smile: 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.
     
  5. Feb 10, 2013 #4
    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?
     
  6. Feb 11, 2013 #5

    LDP

    User Avatar
    Gold Member

    Indeed, I should have said "only odd primes".
    Good catch.:approve:
    I will add some more observations on this topic as time permits.
     
  7. Feb 12, 2013 #6
    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Pisano Periods - Fibonacci Numbers mod p
  1. Polynomials (mod p) (Replies: 3)

  2. Integers mod p (Replies: 4)

  3. X² + y² = 1 (mod p) (Replies: 7)

  4. 2^k + n (mod p) (Replies: 0)

Loading...