Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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,

share|improve this question
1  
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
1  
That's correct (except for $f_3=1$, but that's immaterial to the proof anyway). –  Alex B. Mar 1 '11 at 7:25
1  
You are right... –  user17762 Mar 1 '11 at 7:26
    
@all: Thank you. I corrected the typo. –  Chan Mar 1 '11 at 7:42
3  
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
add comment

1 Answer 1

up vote 6 down vote accepted

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

share|improve this answer
    
Thank you. –  Chan Mar 1 '11 at 7:43
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.