Задать вопрос
15 ноября, 23:23

Докажите, что для любого натурального m существует число Фибоначчи Fn (n ≥ 1), кратное m

+5
Ответы (1)
  1. 16 ноября, 01:50
    0
    Числа Фибоначчи - последовательность чисел, задаваемая рекуррентно: F (n + 2) = F (n + 1) + F (n), F (0) = 0, F (1) = 1.

    Выпишем остатки первых m^2 + 2 чисел Фибоначчи, начиная с нулевого, при делении на m. Поскольку всего различных остатков при делении на m ровно m, то различных пар остатков не более m^2. Пар соседних остатков m^2 + 1, тогда по принципу Дирихле найдутся две пары соседних чисел Фибоначчи, которые дают соответственно равные остатки при делении на m. Так как по двум остаткам последовательность однозначно восстанавливается в обоих направлениях, последовательность остатков периодичная, и найдётся число Фибоначчи с номером, не превосходящим m^2 + 2, дающее такой же остаток при делении на m, что и F (0) = 0, оно будет делиться на m.
Знаете ответ?
Сомневаетесь в ответе?
Найдите правильный ответ на вопрос ✅ «Докажите, что для любого натурального m существует число Фибоначчи Fn (n ≥ 1), кратное m ...» по предмету 📘 Математика, а если вы сомневаетесь в правильности ответов или ответ отсутствует, то попробуйте воспользоваться умным поиском на сайте и найти ответы на похожие вопросы.
Смотреть другие ответы