Prove that at least one of the first $10^6$ Fibonacci numbers is divisible by 1000 I need to prove that at least one of the first 1000000 Fibonacci numbers is divisible by 1000 and I really don't know how to approach it
 A: Assume that the $10^6$ first Fibonacci numbers aren't divisble by $1000 \color{blue}{(*)}$, in other words,
$$a_n \equiv k \pmod {1000} \qquad \forall n$$
with $k \in {1,...,999}$
From the $(999\times 999+\color{red}2)$ first Fibonacci numbers, we can construct $999\times999+\color{red}1$ couples $(a_n,a_{n+1})$. Applying the Pigeonhole principle where there are $999\times999+1$ pigeons but only $999\times999$ pigeonholes, there exists $(n,m)$ such that $n,m<(999\times 999+2)$ and
$$(a_n,a_{n+1}) \equiv (a_m,a_{m+1}) \pmod {(1000,1000)} \tag{1}$$
From $(1)$, we can deduce that the Fibonacci sequence is periodic of order of at most $(m-n)$ (which is less than or equal to $(999\times 999+2)$).
As the two first values of Fibonacci sequence is $(a_1,a_2) = (1,1)$, and because $10^6 >(999\times 999+2)$ then from the periodicity of order at most $(m-n)$ of the sequence, we deduce that $l =  (m-n)+\color{red}1 < 10^6$  satisfies
$$(a_l,a_{l+1}) \equiv (a_1,a_2) =(1,1) \pmod {(1000,1000)} \tag{1}$$
Hence, $a_{l-1} =a_{l+1}-a_l \equiv 0 \pmod {1000} \implies$ contradiction to $\color{blue}{(*)}$.
We can then conclude that at least one of the $10^6$ first Fibonacci numbers is divisble by $1000$ (Q.E.D).
