Задача
NT-B2-M12-P020 Делимость некоторого числа Фибоначчи на \(m\)
#20
★★★★★ Уровень 5 из 5
Докажите, что для любого \(m\ge2\) существует положительное \(n\), для которого \(m\mid F_n\). Более того, таких \(n\) бесконечно много.
Используйте периодичность пар \((F_n,F_{n+1})\) по модулю \(m\) и возвращение к \((0,1)\).
По модулю \(m\) последовательность пар \((F_n,F_{n+1})\) чисто периодична и начинается с \((0,1)\). Значит, существует период \(T>0\), для которого \((F_T,F_{T+1})\equiv(0,1)\pmod m\). В частности, \(F_T\equiv0\pmod m\).
Так как та же пара повторяется через каждый период, \((F_{qT},F_{qT+1})\equiv(0,1)\pmod m\) для всех \(q\ge1\). Поэтому \(m\mid F_{qT}\) для бесконечно многих \(qT\).
Финальная задача хорошо закрывает идею “конечное число состояний даёт существование”.