geo
Posts:
38
Registered:
6/19/08


Re: periods of fibonaccilike 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_(n1) + x_(n2) 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) != p1. > > (2) If p = 1 or 4 (mod 5) then m(p) = M(p) iff M(p) = p1. > > quasi
A nice little exercise.
Let T be the 2x2 matrix T= (0 1) (1 1) Then T has an inverse T^(1)= (p1 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

