, 2013

Let $m$ be a positive integer and consider the infinite set of pairs $(F_{k}, F_{k+1})$, for $k \in \mathbb{N}$. By the pigeonhole principle, there exists a pair $(a, b)$ of integers $0 \leq a, b \leq m-1$ and an infinite sequence of integers $0<k_{1}<k_{2}<\cdots$ such that
$$(F_{k_{i}}, F_{k_{i}+1}) \equiv (a, b) \quad \bmod m, \text{ for all } i \geq 1.$$
Therefore
$$(F_{k_{i}-1}, F_{k_{i}}) = (F_{k_{i}+1}-F_{k_{i}}, F_{k_{i}}) \equiv (b-a, a) \bmod m, \text{ for all } i \geq 1.$$
We keep descending in this way until we get
$$(F_{k_{i}-k_{1}+2}, F_{k_{i}-k_{1}+3}) \equiv (F_{2}, F_{3}) \equiv (1,2) \quad \bmod m, \quad \text{ for all } i \geq 1.$$
Let $n_{i}=k_{i}-k_{1}+2$, for all $i \geq 1$. Clearly, the infinite sequence $2=n_{1}< n_{2}<\cdots$ is increasing and we have
$$\begin{gathered} F_{n_{i}}+2 \equiv F_{2}+2 \equiv 3 \bmod m, \quad F_{n_{i}+1}+1 \equiv F_{3}+1 \equiv 3 \bmod m \\ \text{ and } F_{n_{i}+2} \equiv F_{n_{i}+1}+F_{n_{i}} \equiv F_{3}+F_{2} \equiv 3 \bmod m \end{gathered}$$