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

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

My attempt:

We have $f_1 = 1, f_2 = 1, f_3 = 2...$. So obviously $\gcd(f1, f2) = 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 in the right track?
Any feedback would be greatly appreciated.

Thanks,

-
Your argument is correct! However, you have a minor typo - you wrote $f_3=1$, instead of $f_3=2$. – Zev Chonoles Mar 1 '11 at 7:25
That's correct (except for $f_3=1$, but that's immaterial to the proof anyway). – Alex B. Mar 1 '11 at 7:25
You are right... – user17762 Mar 1 '11 at 7:26
@all: Thank you. I corrected the typo. – Chan Mar 1 '11 at 7:42
More generally, $\mbox{gcd}(f_m,f_n)=f_{\mbox{gcd}(m,n)}$. See en.wikipedia.org/wiki/… – lhf Mar 1 '11 at 14:56

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

-
Thank you. – Chan Mar 1 '11 at 7:43