Tell me more ×
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.
up vote 7 down vote favorite

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
1  
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

1 Answer

up vote 1 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

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.