Relatively Prime Fibonacci numbers We can call the $x$th Fibonacci number Fib($x$).  What's the best asymptotic lower bounds on the amount of relatively prime Fibonacci numbers between Fib($n$) and Fib($n+m$)?
In other words, if we take the $m$ Fibonacci numbers that lie between Fib($n$) (inclusive) and Fib($n+m$), what is the maximally sized set of these numbers can be pairwise relatively prime to each other, in terms of $n$ and $m$?  Of course, I'm looking for some sort of asymptotic bounds - more specifically, a big Omega bound, but we are allowed to pick from any of the $m$ Fibonacci numbers in the sequence, in order to make this bound larger.  Note that I'm looking for the maximally sized set, but in the worst case.
 A: Although this appears to be intrinsically a question about Fibonacci numbers, in fact the Fibonacci numbers are a guise. The key aspect to notice here is that
$$ \gcd(Fib(n), Fib(m)) = Fib(\gcd(n,m)).$$
(This is proved, for instance, in this other post on this site).
Thus $Fib(n)$ and $Fib(m)$ are relatively prime exactly when $\gcd(m,n) = 1$ or $2$. Your question is now a question about relatively prime (or divisible by exactly $2$) sets of numbers.
The relevant question to ask is the following.

What is the size of the largest subset $S \subseteq [m, n]$ such that $x,y \in S$ implies that $\gcd(x,y) = 1$ or $\gcd(x,y) = 2$?

A clear lower bound is the number of primes between $m$ and $n$, $\pi(n) - \pi(m)$. In fact, one can also use numbers which are twice a prime, so a slightly better lower bound is $\pi(n) - \pi(m/2)$. Asymptotically, if $n - m = X$, then this guarantees $X / \log X$ as a lower bound.
It is not clear to me how much better you can actually do. This seems to me to be a nice, hard problem --- precisely the sort of thing that Erdos or Pomerance would be interested in.
