Search All of the Math Forum:

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

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

 Messages: [ Previous | Next ]
 geo Posts: 38 Registered: 6/19/08
Re: periods of fibonacci-like sequences mod p
Posted: Feb 3, 2011 3:53 PM

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
T=
(0 1)
(1 1)
Then T has an inverse
T^(-1)=
(p-1 1)
( 1 0)

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

(a,b)T=(b,a+b).

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

Date Subject Author
2/3/11 quasi
2/3/11 achille
2/3/11 quasi
2/3/11 aayushbabu
2/3/11 Pubkeybreaker
2/3/11 quasi
2/3/11 quasi
2/3/11 quasi
2/3/11 quasi
2/3/11 achille
2/4/11 quasi
2/4/11 achille
2/4/11 quasi
2/3/11 geo
2/3/11 quasi