# Gcd of Fibonacci and Catalan

Let $F_n=1,1,2,3,5,\ldots$ (starting with $n=1$) be the Fibonacci sequence and let $C_n=\frac{1}{n+1}\binom{2n}{n}$ be the Catalan sequence. Define $B_z$ to be the cardinality of $$B_z := \#\bigl\{ n \leq z | \gcd(F_n,C_n)=1 \bigr\}.$$ It seems $$\lim_{z\to\infty} \frac{B_z}{z}=\frac14.$$ Posted a related question here: https://math.stackexchange.com/questions/2131648/gcd-of-catalan-and-fibonacci-numbers, but it got no answer and, thinking a bit about it, the question might be more research related than elementary (but I have no real training in such questions). So question is: Does $B_z/z$ converge, and if so, to what? Here some values of $g_z := B_z/z$, $$g_{1000}=\frac{71}{250}=0.284, \quad g_{2000}=\frac{13}{50}=0.260, \quad g_{3000}= \frac{187}{750}\approx0.249, \quad g_{4000}=\frac{979}{4000}\approx0.245.$$ The sequence of integers such that the gcd is one starts with $$1,2,3,4,5,8,10,11,13,14,17,22,23,25,\ldots$$ and is probably not known in the sequence database.

• Are you assuming $F_0 = F_1 = 1$ or $F_1 = F_2 = 1$? – D. Ror. Feb 7 '17 at 18:10
• $F_1=F_2=1$.Long comment needed. – Mare Feb 7 '17 at 18:12
• Yes -- in the stackexchange question there was confusion caused by the fact that if you re-index the Fibonacci sequence then this completely changes $B_z$. So perhaps why not list the first few $F_n$ and $C_n$, plus the first few $n$ such that the gcd is 1, so everyone knows we're talking about the same question. – Kevin Buzzard Feb 7 '17 at 18:13
• No, I justed needed to add something because $F_1=F_2=1$ was too short for a comment. – Mare Feb 7 '17 at 18:14
• No but honestly, put it into the question, so people can just read the MO question (and not the MO comments, or the SE question, or the SE comments etc) -- you will be more likely to get a response that way. In particular the first few $n$ such that the gcd is 1 will be a very useful thing to have in the question so that people know quickly if they have made a mistake. – Kevin Buzzard Feb 7 '17 at 18:17

This is a bit overlong for a comment, and not really an answer, but includes some information about a related problem that might offer approaches to this one. In particular, the fact that the Fibonacci sequence is a divisibility sequence means that gcd properties involving $F_n$ are tied into properties for $F_m$ for $m\mid n$. So you might try looking at the proportion of primes in your set.
The Fibonacci sequence is a linear recursion and a divisibility sequence. For a similar question in which one takes two Fibonacci-type sequences, there are conjectures, but not even an inkling of a proof. For example, Ailon and Rudnick conjectured that $$\{n\ge1 : \gcd(2^n-1,3^n-1)=1\}$$ is infinite, and I published a somewhat dubious heuristic argument that $$\text{Density}\Bigl(\{p~\text{prime}:\gcd(2^p-1,3^p-1)=1\}\Bigr)=1.$$ (The density over all $n\in\mathbb{N}$ seems harder to guess.) More generally, due to the divisibility property of these sequences, for $a,b\ge2$ multiplicatively independent, it is natural to look at $$\{n\ge1 : \gcd(a^n-1,b^n-1)=\gcd(a-1,b-1)\}.$$ I'll also mention that Ailon and Rudnick proved a stronger version of their conjecture when one replaces the integers $a$ and $b$ with polynomials $a(T),b(T)\in\mathbb{C}[T]$.
• There is a good reason that Joe Silverman brought in those gcd problems: for each prime $p$ there is smallest integer $\alpha(p)$ such that $\nu_p(F_{\alpha(p)})=1$. With this number, $\nu_p(F_{n\cdot\alpha(p)})=\nu_p((p+1)^n-1)$ and $\nu_p(F_m)=0$ (whenever $\alpha(p)$ does not divide $m$). Of course, $\nu_p((p+1)^n-1)=\nu_p(pn)$ but that is not my point. The intent is to indicate that $x^n-1$ enters the picture of divisibility of the Fibonacci number. – T. Amdeberhan Feb 8 '17 at 4:39