Prove that any two consecutive terms of the Fibonacci sequence are relatively prime

Question

Prove that any two consecutive terms of the Fibonacci sequence are relatively prime.

My attempt:

We have $f_1 = 1, f_2 = 1, f_3 = 2, \dots$, so obviously $\gcd(f_1, f_2) = 1$.
Suppose that $\gcd(f_n, f_{n+1}) = 1$; we will show that $\gcd(f_{n+1}, f_{n+2}) = 1$. Consider $\gcd(f_{n+1}, f_{n+2}) = \gcd(f_{n+1}, f_{n+1} + f_n)$ because $f_{n+2} = f_{n+1} + f_n.$
Then $\gcd(f_{n+1}, f_{n+1} + f_n) = \gcd(f_{n+1}, f_{n}) = 1$ (gcd property).

Hence, $\gcd(f_n, f_{n+1}) = 1$ for all $n > 0$.

Am I on the right track?
Any feedback would be greatly appreciated.

Thanks,

Answer 1

Congratulations, you have solved it. You have used the fact that $\gcd(a+b,b)=\gcd(a,b)$

Answer 2

Using induction/modular arithmetic:

For n = 1, we see that $F_n$ and $F_{n+1}$ are relatively prime.

For the inductive step, we assume $F_n$ and $F_{n+1}$ are relatively prime, and show this implies $F_{n+1}$ and $F_{n+2}$ are relatively prime.

By the inductive assumption, for any prime $p$ for which $p|F_{n+1}$, $p∤F_n$. With modular arithmetic, this statement becomes $$F_{k+1} ≡ 0⠀mod(p)$$ and $$ F_k ≢ 0⠀mod(p)$$Using the definition of the Fibonacci sequence, we can change the first congruence to $$F_{k+2} - F_k ≡ 0⠀mod(p)$$ $$F_{k+2} ≡ F_k≢ 0⠀mod(p)$$ Modular congruence is transitive (this is pretty clear, i.e. since $3≡7≡15⠀mod(4),⠀ 3≡15⠀mod (4)$.) Thus $F_{k+2} ≢0⠀mod(p)$, meaning $p∤F_{k+2}$ and $F_{n+1}$ and $F_{n+2}$ are relatively prime.