Do Fibonacci numbers form a complete residue system in every modulus? I want to show that:
$$\forall x,m\ \exists n:x\equiv_mF_n$$
I assume that one can prove this by the pigeonhole principle, but I couldn't manage to find a series of $m+1$ numbers that each want to occupy a different number.
 A: No, because:
If $m=11$, then the Fibonacci numbers are $\pmod {11}$
$$ 0,1,1,2,3,5,8,2,10,1,0,1,1,\dots $$
so $x = 4,6,7,9$ are never reached.
A: This is not true modulo 8, a computation shows that no Fibonacci number is equivalent to $ 4$ or $6 \mod 8$.

You can actually use the pigeonhole principle to show that this is never true modulo a prime modulus $m$ which satisfies $m\equiv  1$ or $4\mod 5$, i.e. there is always some residue $a$ such that
$$ a \not\equiv F_n \mod m \quad\text{for any }n.$$
Hint: Recall the closed form equation for the Fibonacci numbers
$$ F_n = A\phi^n + B\bar{\phi}^n \quad$$
where $\phi = \frac12(1+\sqrt{5})$ is the golden ratio and $\bar{\phi} = \frac12(1 -\sqrt{5})$ is its Galois conjugate, and $A$ and $B$ are constants which aren't important right now.

Proof: If the prime $m$ satisfies the above congruence condition modulo $5$, then by quadratic reciprocity the numbers $\pm\sqrt{5}$ are in the finite field $\mathbb F_m$, and hence $\phi, \bar \phi \in \mathbb F_m$. 
Since the multiplicative group modulo $m$ has order $\#\mathbb F_m^\times = m-1$, 
the closed form expression above implies that modulo $m$ the Fibonnaci numbers are periodic with period (dividing) $m-1$.
Thus there can be at most $m-1$ distict residues appearing in $\{F_n \mod m\}_n$.
On the other hand if $m \equiv 2,3$ modulo $5$ (and $m \neq 5$), 
the numbers $\phi, \bar\phi$ lie in the quadratic extension $\mathbb F_{m^2}$, and the Fibonacci numbers $\{F_n \mod m\}_n$ have period $m^2 - 1$. So the pigeonhole principle doesn't help in this case.
A: Values with a complete residue system $\{0, 1, \dots, n-1 \}$ are any numbers of the form 
$$5^k, 2 \cdot 5^k, 4 \cdot 5^k, 3^j 5^k, 6 \cdot 5^k, 7 \cdot 5^k, 14 \cdot 5^k$$
with $k \ge 0, j \ge 1$.  
Sources (from A079002): 


*

*S. A. Burr, On moduli for which the Fibonacci numbers contain a complete system of residues, Fibonacci Quarterly, 9 (1971), 497-504.

*Cheng Lien Lang and Mong Lung Lang, Fibonacci system and residue completeness, arXiv:1304.2892 [math.NT], 2013.

A: The Fibonacci sequence modulo $n$ is periodic, because a pair of consecutive numbers will necessarily repeat after at most $n^2$ steps.
If $p>5$ is prime and $5$ is a quadratic residue modulo $p$, which means $5$ is a square modulo $p$, then, working in the $p$-element field, the characteristic equation of the recurrence $a_{n+2}-a_{n+1}-a_n=0$ has roots
$$
r_+=\frac{1+u}{2}\qquad r_-=\frac{1-u}{2}
$$
where $u^2=5$, so the general term has the form
$$
\alpha r_+^n+\beta r_-^n
$$
Since we want $a_0=0$ and $a_1=1$, we need
\begin{cases}
\alpha+\beta=0\\
\alpha r_+ +\beta r_-=1
\end{cases}
that is, $\beta=-\alpha$ and $\alpha=1/u$. Therefore
$$
a_n=\frac{1}{u}(r_+^n-r_-^n)
$$
Since by little Fermat we have $s^p=s$ for every $s$, the period is at most $p-1$ and $1$ appears twice in the period, so at least two remainders cannot appear.
