Задача
Докажите справедливость следующих утверждений:
а) 2 | Fn ⇔ 3 | n;
б) 3 | Fn ⇔ 4 | n;
в) 4 | Fn ⇔ 6 | n;
г) Fm | Fn ⇔ m | n при m > 2.
Решение
а) - в) Выписав последовательности остатков от деления Fn на 2, 3 и 4: 1, 1, 0, 1, 1, ...; 1, 1, 2, 0, 2, 2, 1, 0, 1, 1, ...; 1, 1, 2, 3, 1, 0, 1, 1, ...; видим, что они имеют периоды 3, 8 и 6 соответственно, причём во второй последовательности нули идут на каждом четвёртом месте. г) Дополним числа Фибоначчи числом F0 = 0. Из тождества Fn+m = Fn–1Fm + FnFm+1, следует, что Fn+m ≡ FnFm+1 ≡ FnFm–1 (mod Fm). Отсюда получаем 
Осталось заметить, что 0 < Fm–1 < Fm и 0 < Fr < Fm при r > 0.
Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь
Комментариев нет