Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

This question already has an answer here:

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

marked as duplicate by Bill Dubuque elementary-number-theory May 9 '15 at 15:09

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new 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:… – 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
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|cite|improve this answer

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