How to prove gcd of consecutive Fibonacci numbers is 1? [duplicate]

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

How to prove 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.

Solution 1:

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$.

Solution 2:

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$.

Solution 3:

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