Задача
NT-B2-M12-P019 НОД чисел Фибоначчи
#19
★★★★★ Уровень 5 из 5
Докажите, что \(\gcd(F_m,F_n)=F_{\gcd(m,n)}\) для всех положительных \(m,n\), где \(F_0=0\), \(F_1=1\).
Докажите евклидов шаг: \(\gcd(F_m,F_n)=\gcd(F_n,F_{m-n})\) при \(m>n\).
Пусть \(m>n\). Из тождества \(F_m=F_{m-n}F_{n+1}+F_{m-n-1}F_n\) следует \(F_m\equiv F_{m-n}F_{n+1}\pmod{F_n}\). Известно, что \(\gcd(F_{n+1},F_n)=1\), поэтому \(\gcd(F_m,F_n)=\gcd(F_{m-n},F_n)\). Это ровно шаг алгоритма Евклида для индексов.
Повторяя шаг, получаем \(\gcd(F_m,F_n)=\gcd(F_g,F_0)\), где \(g=\gcd(m,n)\). Так как \(F_0=0\), это равно \(F_g\).
Если класс не знает \(\gcd(F_{n+1},F_n)=1\), его надо доказать отдельно тем же евклидовым шагом.