Fibonacci numbers?

Question

Show that, for any two elements m and n in N, gcd(f_(m), f_(n)) = f_gcd(m,n)


I know this is a simple proof, but I can't figure it out.

Can anyone help?

_ indicats sub

f sub(_) m

Answer 1

I know that the proof involves induction... So for your base step you have gcd(1,1)=f(gcd(1,2))=1 is true. For the inductive step you will need that fn + f(n+1)=f(n+2).

Answer 2

I know that I've done it before, but I can't remember how. Maybe Wikipedia can help:

Common factors

Any two consecutive Fibonacci numbers are relatively prime. Suppose that Fn and Fn+1 have a common factor g. Then Fn−1 = Fn+1 – Fn must also be a multiple of g; and by induction the same must be true of all lower Fibonacci numbers. But F1 = 1, so g = 1.

http://en.wikipedia.org/wiki/Fibonacci_number#Common_factors


Other identities include relationships to the Lucas numbers, which have the same recursive properties but start with L0=2 and L1=1. These properties include F2n=FnLn

Answer 3

teell us what is f_, without this information we can not reply your question.