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

Printable View

- November 23rd 2009, 05:16 AMzhushpRelatively 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 - November 23rd 2009, 07:01 AMaman_cc
- November 23rd 2009, 07:42 AMzhushp
- November 23rd 2009, 07:53 AMaman_cc
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.