Question

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

Answer 1

Числа Фибоначчи – последовательность чисел, задаваемая рекуррентно: 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.

Answer 2

Для доказательства данного утверждения воспользуемся принципом математической индукции.

Базовый случай: Пусть m = 1. Тогда первое число Фибоначчи F1 = 1, которое является кратным 1. Таким образом, базовый случай верен.

Шаг индукции: Предположим, что для некоторого натурального k выполняется условие, что существует число Фибоначчи Fk, которое кратно m.

Докажем, что тогда существует число Фибоначчи F(k+1), которое также кратно m.

Используем рекуррентное соотношение для чисел Фибоначчи: F(n) = F(n-1) + F(n-2).

Рассмотрим два случая:

1) Если Fk+1 кратно m, то утверждение доказано.

2) Если Fk+1 не кратно m, то Fk кратно m (по предположению индукции). Также, Fk-1 кратно m (так как Fk+1 = Fk + Fk-1, и Fk+1 не кратно m).

Тогда, по определению чисел Фибоначчи, Fk+2 = Fk+1 + Fk кратно m (так как сумма двух чисел, кратных m, также будет кратной m).

Таким образом, в обоих случаях доказано, что существует число Фибоначчи F(k+1), которое кратно m.

Таким образом, по принципу математической индукции для любого натурального m существует число Фибоначчи Fn (n ≥ 1), кратное m.