nt.number theory – Fibonacci with seeds, modulo $n$

We can completely classify modulo which $n$ there is a surjective sequence. Indeed, I claim that $text{fib}_{n, x_0, x_1}$ is surjective for some seed values $x_0,x_1$ iff the usual Fibonacci sequence $F_k$ is surjective modulo $n$. As stated on OEIS, this happens precisely when $n$ is of one of the forms $5^k,2cdot 5^k,4cdot 5^k,3^jcdot 5^k,6cdot 5^k,7cdot 5^k,14cdot 5^k$.

One implication is obvious. For the other, assume $text{fib}_{n, x_0, x_1}$ is surjective modulo $n$. In particular we have $text{fib}_{n, x_0, x_1}(k)equiv 0pmod n$. Shifting the index we may assume $k=0$, i.e. $x_0=0$. But then we have $text{fib}_{n, x_0, x_1}(k)equiv x_1F_kpmod n$. This sequence is surjective modulo $n$ iff $F_k$ is and $x_1$ is coprime to $n$.


Old answer:

Not necessarily. Let $F_k$ be the regular Fibonacci sequence. Then we have $text{fib}_{n, x_0, x_1}(k)=x_0F_{k+1}+(x_1-x_0)F_kmod n$. Letting $pi(n)$ be the $n$th Pisano period, this implies that $text{fib}_{n, x_0, x_1}$ is periodic with period dividing $pi(n)$. There are plenty of numbers for which $pi(n)<n$, for instance all numbers modulo which $x^2-x-1$ has a root (as by Binet’s formula and Euler’s theorem we then have $pi(n)midvarphi(n)<n$). For such $n$ the sequence cannot be surjective.