23
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ 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? $\endgroup$ – Harry Richman Dec 10 '17 at 20:51
  • 4
    $\begingroup$ 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. $\endgroup$ – Harry Richman Dec 10 '17 at 20:57
  • 2
    $\begingroup$ 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$? $\endgroup$ – Harry Richman Dec 10 '17 at 20:58
  • 1
    $\begingroup$ Yes I do see it now. Thanks $\endgroup$ – LionCoder Dec 10 '17 at 21:19
  • 8
    $\begingroup$ 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. $\endgroup$ – Jeppe Stig Nielsen Dec 10 '17 at 22:16
35
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – LionCoder Dec 10 '17 at 20:51
  • 31
    $\begingroup$ 11 is a prime.. $\endgroup$ – Exodd Dec 10 '17 at 20:51
  • 2
    $\begingroup$ @LionCoder: Most likely, you were supposed to prove that for every modulus $m$, there's a Fibonacci number congruent to $0$ mod $m$. $\endgroup$ – user2357112 supports Monica Dec 11 '17 at 1:24
26
$\begingroup$

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.

$\endgroup$
13
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Harry Richman Dec 10 '17 at 21:53
  • $\begingroup$ @HarryRichman Yes, I counted wrong. $\endgroup$ – egreg Dec 10 '17 at 21:59
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.