Pisano Periods - Fibonacci Numbers mod p

  • Thread starter LDP
  • Start date
  • Tags
    Numbers
In summary: A test for certain composites is suggested.In summary, we discussed the properties of the Pisano Period and its relationship to primes, particularly those that are congruent to 2 or 3 modulo 5. We also observed that the Pisano Period for primes ending in 3 or 7 may be a useful test for certain composites. Further research and analysis on this topic is needed to fully understand its implications and applications.
  • #1
LDP
Gold Member
3
0
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:
Physics news on Phys.org
  • #2
LDP said:
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 don't know what that means. Can you give an example?
 
  • #3
: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.
 
  • #4
LDP said:
: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.

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?
 
  • #5
ramsey2879 said:
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.:approve:
I will add some more observations on this topic as time permits.
 
  • #6
ramsey2879 said:
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.
 

1. What are Pisano periods?

Pisano periods are the period lengths in which a sequence of numbers modulo a prime number repeats itself. In other words, it is the smallest positive integer m for which the Fibonacci numbers mod p repeat in a cyclic pattern.

2. What are Fibonacci numbers mod p?

Fibonacci numbers mod p are the sequence of Fibonacci numbers where each number is reduced to its remainder when divided by a prime number p. This results in a finite sequence of numbers that will eventually repeat in a cyclic pattern.

3. Why are Pisano periods important?

Pisano periods are important because they provide a way to calculate large Fibonacci numbers modulo a prime number without having to compute all the previous Fibonacci numbers. This is useful in many applications, such as cryptography and number theory.

4. How are Pisano periods calculated?

Pisano periods can be calculated using various methods, such as using the properties of modular arithmetic or using the generalized Fibonacci sequence. The specific method used will depend on the prime number and the given value of p.

5. What are some real-life applications of Pisano periods?

Pisano periods have many practical applications, such as in cryptography where they are used to generate secure pseudo-random numbers. They are also used in algorithms for finding the greatest common divisor of two numbers and in determining the period length of repeating decimals. Additionally, Pisano periods have applications in the fields of economics, biology, and computer science.

Similar threads

  • Linear and Abstract Algebra
Replies
1
Views
730
  • Precalculus Mathematics Homework Help
Replies
17
Views
2K
  • Precalculus Mathematics Homework Help
Replies
16
Views
2K
  • Linear and Abstract Algebra
Replies
2
Views
1K
  • Calculus and Beyond Homework Help
Replies
16
Views
1K
Replies
8
Views
858
Replies
2
Views
1K
  • Precalculus Mathematics Homework Help
Replies
5
Views
2K
  • Math Proof Training and Practice
3
Replies
100
Views
7K
  • Set Theory, Logic, Probability, Statistics
Replies
2
Views
5K
Back
Top