# 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), 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)). For such $$n$$ the sequence cannot be surjective.

Posted on Categories Articles