Предмет: Математика,
автор: nziltzov
Докажите, что для любого натурального m существует число Фибоначчи Fn (n ≥ 1), кратное m
Ответы
Автор ответа:
3
Числа Фибоначчи – последовательность чисел, задаваемая рекуррентно: 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^2 + 2 чисел Фибоначчи, начиная с нулевого, при делении на m. Поскольку всего различных остатков при делении на m ровно m, то различных пар остатков не более m^2. Пар соседних остатков m^2 + 1, тогда по принципу Дирихле найдутся две пары соседних чисел Фибоначчи, которые дают соответственно равные остатки при делении на m. Так как по двум остаткам последовательность однозначно восстанавливается в обоих направлениях, последовательность остатков периодичная, и найдётся число Фибоначчи с номером, не превосходящим m^2 + 2, дающее такой же остаток при делении на m, что и F(0) = 0, оно будет делиться на m.
Похожие вопросы
Предмет: Математика,
автор: anastasiyazhushma
Предмет: Математика,
автор: antonsedyhk
Предмет: Русский язык,
автор: gzedeninov
Предмет: Физика,
автор: Аноним
Предмет: Математика,
автор: Hidra44444466788