Теоретико-числовые свойства чисел Фибоначчи

(a) Запишем последовательность чисел Фибоначчи в системе остатков по модулю 5:

В последовательности Фибоначчи каждое число определяется двумя предыдущими, поэтому, если пара последовательных чисел повторится, последовательность станет циклической. Тогда длина предпериода или периода не может превышать Остаётся проверить, появится ли в периоде остаток 0 по модулю 5. Выше уже выписана последовательность; можно заметить, что период равен 20 и в нём содержится остаток 0. Следовательно, в последовательности Фибоначчи существует бесконечно много чисел, кратных 5.

(b) Будем рассматривать числа последовательности Фибоначчи по модулю 2024. Из пункта (a) понятно, что здесь также будет период, и его длина не более Назовём состоянием пару последовательных чисел. Состояние однозначно определяет следующее число — и предыдущее — Это означает, что предпериода нет, так как в каждое состояние мы однозначно попадаем из состояния Значит, период начинается с Пусть последний остаток в периоде равен тогда:

Но так как то и есть искомое число, кратное 2024. Следовательно, в последовательности Фибоначчи существует бесконечно много чисел, кратных 2024.