[Math] 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)$