Consider set $A:= \{F_{n} \mid n, \, 1 \leq n \leq 1000002\}$ where $F_{n}$ denotes the $n$th Fibonacci number.
Prove that exist at least two numbers $F_a$ and $F_b$, such that $F_a,F_b \in A$ and $F_a$, $F_b$ are divisible by $1000$.
I trying to use the Dirichlet's box principle, but I have problem, how to define pigeonhole.
Every sixth element is divisible by $8$ and every $125^{th}$ is divisible by $125$, just by computation. Then every $750^{th}$ is divisible by $1000$
Note that we just have to find the first element divisible by any prime power. The next number after that may not be $1$, but the recurrence is linear. In this example, $F_7\equiv 5 \pmod 8$, but the next block is just the first block multiplied by $5$ and $0 \cdot 5=0$