Recall that the Fibonacci numbers are defined by \(F_0 = 1, F_1 = 1\), and then \[F_n = F_{n-1} + F_{n-2} \quad \text{for integers } n \geq 2.\]
Prove that any two successive Fibonacci numbers \(F_n, F_{n+1}\) are relatively prime.
Solution
1. For every \(n\ge1\),\[ \gcd(F_{n+1},F_n)=\gcd(F_n,F_{n-1}). \]
Since \(F_{n+1}=F_n+F_{n-1}\), \[ \gcd(F_{n+1},F_n) =\gcd(F_n+F_{n-1},F_n) =\gcd(F_{n-1},F_n), \] using the Euclidean identity \(\gcd(a+b,b)=\gcd(a,b)\).
2. Iterating 1 gives\[ \gcd(F_{n+1},F_n)=\gcd(F_1,F_0)=1 \]for every \(n\ge0\).
For \(n=0\), this is immediate from \(F_0=F_1=1\). For \(n\ge1\), repeated application of 1 lowers the indices until the pair \((F_1,F_0)\) is reached.
3. Hence every two successive Fibonacci numbers are relatively prime.