Задача
NT-B2-M12-P010 Периодичность Фибоначчи
#10
★★★☆☆ Уровень 3 из 5
Пусть \(F_0=0\), \(F_1=1\), \(F_{n+2}=F_{n+1}+F_n\). Докажите, что последовательность \(F_n\) периодична по модулю любого \(m\ge2\).
Рассмотрите пары соседних остатков.
Пары \((F_n,F_{n+1})\) по модулю \(m\) имеют не более \(m^2\) значений, поэтому какая-то пара повторится. Переход \((x,y)\mapsto(y,x+y)\) обратим по модулю \(m\): из \((y,z)\) восстанавливаем \((z-y,y)\). Значит, если пара повторилась, то период продолжается назад до начальной пары \((0,1)\). Следовательно, последовательность периодична с самого начала.
Обратимость отличает Фибоначчи от произвольной рекурсии.