Problem
NT-B2-M12-P019 GCD of Fibonacci Numbers
#19
★★★★★ Level 5 of 5
Prove that \(\gcd(F_m,F_n)=F_{\gcd(m,n)}\) for all positive \(m,n\), where \(F_0=0\), \(F_1=1\).
Prove the Euclidean step: \(\gcd(F_m,F_n)=\gcd(F_n,F_{m-n})\) for \(m>n\).
Let \(m>n\). From \(F_m=F_{m-n}F_{n+1}+F_{m-n-1}F_n\), we get \(F_m\equiv F_{m-n}F_{n+1}\pmod{F_n}\). Since \(\gcd(F_{n+1},F_n)=1\), it follows that \(\gcd(F_m,F_n)=\gcd(F_{m-n},F_n)\). This is exactly the Euclidean step on the indices.
Repeating the step gives \(\gcd(F_m,F_n)=\gcd(F_g,F_0)\), where \(g=\gcd(m,n)\). Since \(F_0=0\), this equals \(F_g\).
If the class has not seen \(\gcd(F_{n+1},F_n)=1\), prove it separately using the same Euclidean step.