Problem
NT-B2-M12-P020 A Fibonacci Number Divisible by \(m\)
#20
★★★★★ Level 5 of 5
Prove that for every \(m\ge2\) there exists a positive \(n\) such that \(m\mid F_n\). Moreover, there are infinitely many such \(n\).
Use periodicity of the pairs \((F_n,F_{n+1})\) modulo \(m\) and the return to \((0,1)\).
Modulo \(m\), the sequence of pairs \((F_n,F_{n+1})\) is purely periodic and starts from \((0,1)\). Hence there is a period \(T>0\) such that \((F_T,F_{T+1})\equiv(0,1)\pmod m\). In particular, \(F_T\equiv0\pmod m\).
The same pair repeats after every period, so \((F_{qT},F_{qT+1})\equiv(0,1)\pmod m\) for all \(q\ge1\). Therefore \(m\mid F_{qT}\) for infinitely many indices \(qT\).
This closing problem nicely captures the idea that finitely many states imply existence.