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.

  • 1
    What is $f_m$, $f_n$?2012-04-25
  • 0
    Why don't you tell us what they are at the beginning.2012-04-25
  • 1
    **Hint.** $F_{kn}$ is divisible by $F_n$2012-04-25
  • 4
    This is most probably a duplicate though I can't find the link right now.2012-04-25
  • 4
    Here is one answer: http://math.stackexchange.com/questions/60340/fibonacci-modular-results/60353#603532012-04-25
  • 0
    There's a step where he states that $(f_{n-m},f_m)=f_{(n-m,m)}$. Is that something that's well-known?2012-04-25
  • 0
    This is mentioned in [Wikipedia article](http://en.wikipedia.org/wiki/Fibonacci_sequence#Divisibility_properties), the Wikipedia article has two references: [this link](http://www.math.hmc.edu/funfacts/ffiles/20004.5.shtml) and this book: Paulo Ribenboim, My Numbers, My Friends, Springer-Verlag 2000, [p.9](http://books.google.com/books?id=EiYvlcimEi4C&pg=PA9).2012-04-25
  • 1
    Josué: The proof is induction on $n+m$, so this is inductive hypothesis you can assume.2012-04-25
  • 0
    @Josué sdcvvc is correct. The induction is on the sum of the indices. Thus $\rm\:(f_{n-m},f_m)=f_{\:(n-m,m)}\:$ follows by the induction, since it has smaller index sum $\rm\:(n-m)+m\: <\: n+m,\:$ by $\rm\:m>0,\:$ by hypothesis. I just edited the post to make it render better in the latest MathJax release.2012-04-25
  • 0
    I understand now. :) Thanks, guys!2012-04-25

1 Answers 1

2

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