# If $m$ and $n$ are positive integers, then $(F_m,F_n)=F_{(m,n)}$.

Edit: The $F$'s are Fibonacci numbers.

I need an idea on how to show the following:

If $m$ and $n$ are positive integers, then $(F_m,F_n)=F_{(m,n)}$.

I believe that using the fact that $F_{m+n}=F_mF_{n+1}+F_nF_{m-1}$ could come in handy. Moreover, Euclid's algorithm may as well be needed. But I am not certain, as there may be better methods to achieve this.

What is $f_m$, $f_n$? –  Daan Michiels Apr 25 '12 at 18:16
Hint. $F_{kn}$ is divisible by $F_n$ –  Arturo Magidin Apr 25 '12 at 18:22
Josué: The proof is induction on $n+m$, so this is inductive hypothesis you can assume. –  sdcvvc Apr 25 '12 at 18:40