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?



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](http://oeis.org/A079002), 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](https://en.wikipedia.org/wiki/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.


