# 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.

• It is true however that for any $m$, there is a nonzero Fibonacci number $F_n$ such that $F_n \equiv 0 \mod m$. Have you seen a proof of this? – Harry Richman Dec 10 '17 at 20:51
• If you compute the sequence of Fibonacci numbers modulo $m$, the sequence will be eventually periodic by the pigeonhole principle-- the sequence is determined by any two consecutive values and there are only $m^2$ such pairs to choose from so one of them must repeat. – Harry Richman Dec 10 '17 at 20:57
• Then, it suffices to show there is a 0 in this periodic part. Do you see why you couldn't get a sequence like $0,1,1,2,3,2,3,2,3,...$ for some $m$? – Harry Richman Dec 10 '17 at 20:58
• Yes I do see it now. Thanks – LionCoder Dec 10 '17 at 21:19
• The $m$ values for which you are right, i.e. those for which the Fibonacci sequence modulo $m$ reaches every value (modulo $m$), are 1, 2, 3, 4, 5, 6, 7, 9, 10, 14, 15, 20, 25, 27, 30, 35, 45, 50, 70, 75, 81, ... (OEIS A079002). You see $m=8$ and $m=11$ are not among them, and people use these $m$ in their counterexamples in the answers. – Jeppe Stig Nielsen Dec 10 '17 at 22:16

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.

• Interesting, thanks! I got this as a fun challenge to try to prove. Could it be that my friend mixed something up? Did he maybe mean only modulo a prime? – LionCoder Dec 10 '17 at 20:51
• 11 is a prime.. – Exodd Dec 10 '17 at 20:51
• @LionCoder: Most likely, you were supposed to prove that for every modulus $m$, there's a Fibonacci number congruent to $0$ mod $m$. – user2357112 supports Monica Dec 11 '17 at 1:24

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.

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.

• Did you mean $p-1$ for the period? According to en.wikipedia.org/wiki/Pisano_period, it's sometimes even smaller, for example when $p = 29$ the period is $14$. – Harry Richman Dec 10 '17 at 21:53
• @HarryRichman Yes, I counted wrong. – egreg Dec 10 '17 at 21:59

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):