2
$\begingroup$

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.

$\endgroup$
10
  • 1
    $\begingroup$ What is $f_m$, $f_n$? $\endgroup$ – Daan Michiels Apr 25 '12 at 18:16
  • 1
    $\begingroup$ Hint. $F_{kn}$ is divisible by $F_n$ $\endgroup$ – Arturo Magidin Apr 25 '12 at 18:22
  • 4
    $\begingroup$ This is most probably a duplicate though I can't find the link right now. $\endgroup$ – lhf Apr 25 '12 at 18:23
  • 4
    $\begingroup$ Here is one answer: math.stackexchange.com/questions/60340/… $\endgroup$ – sdcvvc Apr 25 '12 at 18:30
  • 1
    $\begingroup$ Josué: The proof is induction on $n+m$, so this is inductive hypothesis you can assume. $\endgroup$ – sdcvvc Apr 25 '12 at 18:40
2
$\begingroup$

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

$\endgroup$

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