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

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.

-

## marked as duplicate by Bill Dubuque elementary-number-theoryUsers with the  elementary-number-theory badge can single-handedly close elementary-number-theory questions as duplicates and reopen them as needed. StackExchange.ready(function() { $('.load-dupe-hammer-message').click(function() { if ($('.dupe-hammer-message').is(':visible')) { StackExchange.helpers.removeMessages(); } else { $(this).showInfoMessage('', { messageElement:$('.dupe-hammer-message').clone().removeClass('dno'), transient: false, position: { my: 'bottom left', at: 'top center' } }); } }); }); May 9 at 15:09

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