Thread: Relatively prime and fibonacci

Let integers a,b>0, F(i) denotes the ith Fibonacci number, such as f(1)=1, f(3)=2...
Prove that if a and b are natural number with gcd(a,b)=1, then that gcd(F(a),F(b))=1 too

Originally Posted by zhushp

Let integers a,b>0, F(i) denotes the ith Fibonacci number, such as f(1)=1, f(3)=2...
Prove that if a and b are natural number with gcd(a,b)=1, then that gcd(F(a),F(b))=1 too

Hint: if n|F(a) and n|F(b) then n|F(gcd(a,b))
Can you prove this? Then the above is a corollary of this

Originally Posted by aman_cc

Hint: if n|F(a) and n|F(b) then n|F(gcd(a,b))
Can you prove this? Then the above is a corollary of this

Sorry, i cannot figure this out~

Originally Posted by zhushp

Sorry, i cannot figure this out~

Hint:
1. Let x be the smallest number such that n|F(x)
2. Show n|F(a) IFF x|a, for any a.
3. Thus, in our case, x|a and x|b => x|gcd(a,b) => n|F(gcd(a,b))

So the critical step is step 2. Work it out. Try with few examples first you will get an idea as to what's happening. Then generalize it.