Регистрация
Никита0Скорая0Помощь
03.02.2023 13:29
Математика
Есть ответ 👍

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

260
455
Посмотреть ответы 2

Ответы на вопрос:

Егорка8374
Егорка8374
4,4(5 оценок)
Числа фибоначчи – последовательность чисел, задаваемая рекуррентно: 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.
vvi1310
vvi1310
4,8(42 оценок)

Покрокове пояснення: 3x 3x 3x 3x 3x

Популярно: Математика