Задача
NT-B2-M12-P011 Делимость по индексу
#11
★★★☆☆ Уровень 3 из 5
Докажите: если \(d\mid n\), то \(F_d\mid F_n\).
Покажите, что из \(F_d\mid F_r\) следует \(F_d\mid F_{r+d}\).
Используем тождество \(F_{r+d}=F_{d-1}F_r+F_dF_{r+1}\). Если \(F_d\mid F_r\), то обе части правой суммы делятся на \(F_d\). Поэтому \(F_d\mid F_{r+d}\). Начиная с \(r=d\), по индукции получаем \(F_d\mid F_{2d},F_{3d},\ldots\). Если \(n=td\), то \(F_d\mid F_n\).
Следующий шаг — НОД чисел Фибоначчи.