Do Fibonacci numbers form a complete residue system in every modulus?

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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.