Physics Forums

Recognitions:
Gold Member

## Pisano Periods - Fibonacci Numbers mod p

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$\equiv${2,3}mod 5 so that h(p)$\mid$ 2 p + 2.
Let h(p) denote of the length of the Pisano period.

If D = {d1,d2,d3$\cdots$dk} is the non-empty set of k divisors of 2 p + 2
Then:
h(p) = min[di] such that Fd(i + 1)$\equiv$ 1 mod p
and
1. di ~$\mid$$\frac{1}{2}$ p (p + 1)
2. di ~$\mid$ p + 1
3. di ~$\mid$ 3 (p - 1)

Now let p = a prime such that p$\equiv${1,4}mod 5 so that h(p)$\mid$ p - 1.
If p has a primitive root such that g2$\equiv$ g + 1 mod(p) then h(p) = p - 1.
Note that g2$\equiv$ 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$\cdots$dk} is the non-empty set of k divisors of p - 1.
Let h(p) = min[di] such that Fd(i + 1)$\equiv$ 1 mod p
and
di ~$\mid$ p + 1 and di ~$\mid$ 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) = 2m ↔ m is even
2. h(Fm) = 4m ↔ m is odd

PhysOrg.com  science news on PhysOrg.com  >> Front-row seats to climate change>> Attacking MRSA with metals from antibacterial clays>> New formula invented for microscope viewing, substitutes for federally controlled drug

Blog Entries: 2

Quote by LDP 					 				 				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$\equiv${2,3}mod 5 so that h(p)$\mid$ 2 p + 2. Let h(p) denote of the length of the Pisano period.  If D = {d1,d2,d3$\cdots$dk} is the non-empty set of k divisors of 2 p + 2 Then: h(p) = min[di] such that Fd(i + 1)$\equiv$ 1 mod p anddi ~$\mid$$\frac{1}{2}$ p (p + 1) di ~$\mid$ p + 1 di ~$\mid$ 3 (p - 1)  Now let p = a prime such that p$\equiv${1,4}mod 5 so that h(p)$\mid$ p - 1. If p has a primitive root such that g2$\equiv$ g + 1 mod(p) then h(p) = p - 1. Note that g2$\equiv$ 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$\cdots$dk} is the non-empty set of k divisors of p - 1. Let h(p) = min[di] such that Fd(i + 1)$\equiv$ 1 mod p and di ~$\mid$ p + 1 and di ~$\mid$ floor [ p/2]].  If m is any positive integer > 3 we can write Fn mod Fm where h(Fm) is given by  h(Fm) = 2m ↔ m is even h(Fm) = 4m ↔ m is odd
Interesting to say the least. I am curious as to what is meant by
1. di ~$\mid$$\frac{1}{2}$ p (p + 1)
2. di ~$\mid$ p + 1
3. di ~$\mid$ 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?

Recognitions:      Gold Member  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.

Blog Entries: 2

## Pisano Periods - Fibonacci Numbers mod p

Quote by LDP 					 				 				 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?

Recognitions:
Gold Member

Quote by ramsey2879 					 				 				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.

Blog Entries: 2

Quote by ramsey2879 					 				 				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.

Thread Tools

|                                                               |                               |         |
|---------------------------------------------------------------|-------------------------------|---------|
| Similar Threads for: Pisano Periods - Fibonacci Numbers mod p |                               |         |
| Thread                                                        | Forum                         | Replies |
|                                                               | Programming & Comp Sci        | 4       |
|                                                               | Calculus & Beyond Homework    | 3       |
|                                                               | Linear & Abstract Algebra     | 4       |
|                                                               | Introductory Physics Homework | 1       |
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 36, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.8820688724517822, "perplexity_flag": "middle"}