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

• Relatively prime to what? To each other? What is the maximally sized set of Fibonacci numbers in that range that are all pairwise relatively prime? Is that the question? – Zubin Mukerjee Oct 2 '18 at 19:04
• @ZubinMukerjee: Yes, relatively prime to each other, and yes, the maximally sized set that are all pairwise relatively prime - thank you! – Matt Groff Oct 2 '18 at 19:05
• Note that every third Fib(n) is even, every fourth is divisible by $3$, every fifth by $5$, and that in general every $d^{th}$ is divisible by Fib(d). If indices are coprime so are the Fibonacci numbers (at least with Fib$(1)=1$, Fib$(2)=1$) So this becomes essentially the same problem as picking coprime integers for the indices. – Mark Bennet Oct 2 '18 at 20:04

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.

• I upvoted and will probably accept your nice answer. Just a comment... From this answer and comments: math.stackexchange.com/a/1816646/2626 See the comments below... We can pick a set of primes $p_k$ that are small, and then use the GCD $g$ of all pairwise differences of the primes to get small Fibonacci's $g+p_k$. I doubt this will be the best bound in most cases, but it seems to me to give a reasonable set of Fibonacci numbers. Anyways, thanks for your nice answer, and maybe some Erdos or Pomerance will come along and help! – Matt Groff Oct 3 '18 at 15:37