Complete Generalized Fibonacci Sequences Modulo Primes

Abstract

We study generalized Fibonacci sequences $F_{n+1}=P{F}_n-Q{F}_{n-1}$ with initial values $F_0=0$ and $F_1=1$. Let $P,Q$ be nonzero integers such that $P^2-4Q$ is not a perfect square. We show that if $Q=\pm 1$ then the sequence $\{F_n{\}}_{n=0}^{\infty }$ misses a congruence class modulo every prime large enough. On the other hand, if $Q\ne \pm 1$, we prove that (under GRH) the sequence $\{F_n{\}}_{n=0}^{\infty }$ hits every congruence class modulo infinitely many primes.

13 pages