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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.


share|cite|improve this question
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… – lhf Mar 1 '11 at 14:56
up vote 8 down vote accepted

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

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

Your Answer


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.