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.

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.
