Orbits of Second Order Linear Recurrences over Finite Fields

Let Q be the matrix pmatrix a & b \\ 1 & 0 pmatrix in GL₂(Fq) where Fq is a finite field, and let G be the finite cyclic group generated by Q. We consider the action of G on the set Fq × Fq. In particular, we study certain relationships between the lengths of the non-trivial orbits of G, and their frequency of occurrence. This is done in part by investigating the order of elements of a product in an abelian group when the product has prime power order. For q a prime and $b=1$, the orbits correspond to Fibonacci type linear recurrences modulo q for different initial conditions. We also derive certain conditions under which the roots of the characteristic polynomial of Q are generators of Fq^×. Examples are included to illustrate the theory.