# 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-theory StackExchange.ready(function() { if (StackExchange.options.isMobile) return; $('.dupe-hammer-message-hover:not(.hover-bound)').each(function() { var$hover = $(this).addClass('hover-bound'),$msg = $hover.siblings('.dupe-hammer-message');$hover.hover( function() { $hover.showInfoMessage('', { messageElement:$msg.clone().show(), transient: false, position: { my: 'bottom left', at: 'top center', offsetTop: -7 }, dismissable: false }); }, function() { StackExchange.helpers.removeMessages(); } ); }); }); May 9 '15 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
This is most probably a duplicate though I can't find the link right now. – lhf Apr 25 '12 at 18:23
Here is one answer: math.stackexchange.com/questions/60340/… – sdcvvc Apr 25 '12 at 18:30
Josué: The proof is induction on $n+m$, so this is inductive hypothesis you can assume. – sdcvvc Apr 25 '12 at 18:40

As noted in the comments by sdcvvc, this answer to an earlier question completely answers this question as well.

-