# Relatively prime and fibonacci

• Nov 23rd 2009, 04:16 AM
zhushp
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
• Nov 23rd 2009, 06:01 AM
aman_cc
Quote:

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
• Nov 23rd 2009, 06:42 AM
zhushp
Quote:

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~
• Nov 23rd 2009, 06:53 AM
aman_cc
Quote:

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.