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
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.