Fibonacci with seeds, modulo $n$

Question

Let $n\in\mathbb{N}$ be an integer with $n>1$. For $x_0, x_1 \in \mathbb{Z}/n\mathbb{Z}$ we define the map $\text{fib}_{n, x_0, x_1}: \mathbb{N} \to \mathbb{Z}/n\mathbb{Z}$ by

• $0 \mapsto x_0, 1 \mapsto x_1$, and
• $k \mapsto \text{fib}_{n, x_0, x_1}(k-1) + \text{fib}_{n, x_0, x_1}(k-2)$ for $k\in\mathbb{N}, k\geq 2$.

Question. Given $n\in\mathbb{N}$ with $n>1$, are there $x_0, x_1 \in \mathbb{Z}/n\mathbb{Z}$ such that the map $\text{fib}_{n, x_0, x_1}: \mathbb{N} \to \mathbb{Z}/n\mathbb{Z}$ is surjective?

Answer 1

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,2\cdot 5^k,4\cdot 5^k,3^j\cdot 5^k,6\cdot 5^k,7\cdot 5^k,14\cdot 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 0\pmod 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_k\pmod 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_k\mod 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)\mid\varphi(n)<n$). For such $n$ the sequence cannot be surjective.