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.

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

How to proof it ? Can you help me ?

Let $f_n$ be Fibonacci Sequence. $$(f_{n},f_{n+1})=1,\quad \forall\,n\in\mathbb{N}.$$ Here $(a,b)$ is the greatest common divisor.

share|improve this question
add comment

marked as duplicate by Martin Sleziak, Marvis, sdcvvc, Cameron Buie, Asaf Karagila Oct 16 '12 at 19:14

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

4 Answers

up vote 1 down vote accepted

Hint $\ $ Put $\rm\:a_n = 1 = b_n\:$ in the much more general result below.

Theorem $\ $ If $\rm\:(b_n,\,f_n) = 1\:$ and $\rm\:f_{n+1} = a_n f_n + b_n f_{n-1}\:$ then $\rm\:(f_{n+1},\,f_n) = (f_1,\,f_0).$

Proof $\ $ Clear if $\rm\:n = 0.\:$ Else $\rm\:(f_{n+1},\,f_n) = (a_n f_n\! +\! b_n f_{n-1},\,f_n) = (b_n f_{n-1},\, f_n) = (f_{n-1},\,f_n) = (f_1,\,f_0)$ using induction, and Euclid's Lemma, via the hypothesis that $\rm\:(b_n,f_n) = 1.\ \ $ QED

Remark $\ $ In fact, in the same way, one can prove much more generally that the Fibonacci numbers $\rm\:f_n\:$ comprise a strong divisibility sequence: $\rm\:(f_m,f_n) = f_{(m,n)},\:$ i.e. $\rm\:gcd(f_m,f_n) = f_{\gcd(m,n)}\:.\:$ Yours is the special case $\rm\:m=n\!+\!1.\:$ For a simple proof see my post here.

share|improve this answer
Can we make a similar statement about $(a_n, f_n)$? math.stackexchange.com/questions/527015 –  Unapiedra Oct 16 '13 at 14:40
add comment

You could use induction.

First show $(f_2,f_1) = 1$. Then for $n \geq 2$, assume $(f_n,f_{n-1}) = 1$. Use this and the recursion $f_{n + 1} = f_n + f_{n - 1}$ to show $(f_{n + 1},f_n) = 1$.

share|improve this answer
add comment

If a $d\in\mathbb{N}$ divides $f_n$ and $f_{n+1}$, then $d$ divides also the difference of these two, $f_{n+1}-f_n=f_{n-1}$. Then using $f_n-f_{n-1}=f_{n-2}$, we get $d\mid f_{n-2}$. Repeating this argument again and again, we'll get $d\mid f_{n-3}$, $d\mid f_{n-4}$, and at the end, $d\mid f_{1}$. But $f_1=1$, therefore $d=1$.

share|improve this answer
add comment

Hint: Euclidean algorithm and the recursive definition of the Fibonacci sequence.

share|improve this answer
add comment

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