Every integer divides some Fibonacci number

Idea. The sequence of pairs is eventually periodic, and because the rule is reversible it is *purely* periodic: it returns to its starting pair $(0,1)$.

The pair map. Let $T(a,b)=(b,a+b)$ on $(\mathbb{Z}/m)^2$. Then $(F_n,F_{n+1})\bmod m=T^n(0,1)$. The map $T$ is injective: if $T(a,b)=T(a',b')$ then $b=b'$ and $a+b=a'+b'$, so $a=a'$.

Pigeonhole. The $m^2+1$ pairs $T^0(0,1),\dots,T^{m^2}(0,1)$ cannot all be different, so $T^i(0,1)=T^j(0,1)$ for some $0\le i<j$. Since $T$ is injective, we can cancel one $T$ at a time: $(0,1)=T^{j-i}(0,1)$.

Conclusion. With $p=j-i>0$ we have $(F_p,F_{p+1})\equiv(0,1)\pmod m$. In particular $m\mid F_p$. $\blacksquare$

Remark. The least such $p$ is the "rank of apparition" of $m$: e.g. $5\mid F_5=5$ and $9\mid F_{12}=144$.

Lesson. A recurrence determined by a bijective step, taken modulo $m$, is purely periodic.