The Math Forum

Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Math Forum » Discussions » sci.math.* » sci.math

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: periods of fibonacci-like sequences mod p
Replies: 14   Last Post: Feb 4, 2011 3:45 AM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]

Posts: 38
Registered: 6/19/08
Re: periods of fibonacci-like sequences mod p
Posted: Feb 3, 2011 3:53 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

On Feb 3, 4:51 am, quasi <qu...@null.set> wrote:
> Let p be a prime, p > 5.
> Choose a,b in Z_p, not both 0.
> Define a sequence x_1, x_2, x_3, ... of elements of Z_p by
>    x_1 = a
>    x_2 = b  
>    x_n = x_(n-1) + x_(n-2) if n > 2
> Let m(p), M(p) be the least and greatest possible periods for the
> sequence (x_n), over all choices of initial values a,b
> Conjectures:
> (1) If p = 2 or 3 (mod 5) then m(p) = M(p) != p-1.
> (2) If p = 1 or 4 (mod 5) then m(p) = M(p) iff M(p) = p-1.
> quasi

A nice little exercise.

Let T be the 2x2 matrix
(0 1)
(1 1)
Then T has an inverse
(p-1 1)
( 1 0)

For in initial vector (a,b), not (0,0),
with elements in F, the field of residues mod p,


The sequence

(a,b), (a,b)T, (a,b)T^2,....

is finite because F is finite and
is periodic because T has an inverse.

If 5 is a quadratic residue for p: 5=r^2 mod p,
then T has eigenvalues in F, (1 +/- r)/2,
and the order of T is the (common) order
for those eigenvalues.

If 5 is not a quadratic residue,
then the order of T will be (2p+2)/k,
with k=1 about 80% of the time.

George Marsaglia

Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© The Math Forum at NCTM 1994-2018. All Rights Reserved.