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.

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.

Thanks in advance.

share|improve this question
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

1 Answer 1

up vote 1 down vote accepted

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

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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