|
Название задачи: Делимость чисел Фибоначчи. |
 |
Условие
Докажите справедливость следующих утверждений:
а) 2 | Fn ⇔ 3 | n;
б) 3 | Fn ⇔ 4 | n;
в) 4 | Fn ⇔ 6 | n;
г) Fm | Fn ⇔ m | n при m > 2.
Подсказка
а) - в) Рассмотрите последовательность остатков от деления Fn на 2, 3 и 4.
г) Воспользуйтесь тождеством из задачи 60566.
Решение
а) - в) Выписав последовательности остатков от деления 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.
Источники и прецеденты использования
| книга | |
| Автор | Алфутова Н.Б., Устинов А.В. |
| Год издания | 2002 |
| Название | Алгебра и теория чисел |
| Издательство | МЦНМО |
| Издание | 1 |
| глава | |
| Номер | 3 |
| Название | Алгоритм Евклида и основная теорема арифметики |
| Тема | Алгебра и арифметика |
| параграф | |
| Номер | 4 |
| Название | О том, как размножаются кролики |
| Тема | Классическая комбинаторика |
| задача | |
| Номер | 03.118 |
