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.