# Bound on the number of primitive divisors of the $n$th Fibonacci number

It is a result of Carmichael that for any integer $n > 12$, the Fibonacci number $F_n$ has at least one primitive divisor, that is, a prime factor $p$ such that $p$ does not divide any $F_m$ with $1 \leq m < n$. Indeed, a more general result for all Lucas and Lehmer sequences has been proven by Bilu, Hanrot, and Voutier [1].

But my question is: What about an upper bound for the number of primitive divisors of $F_n$?

If $p$ is a primitive divisor of $F_n$, then it is known that $p \equiv \pm 1 \bmod n$, hence $p \geq n - 1$. Thus, if $P_n$ is the number of primitive divisors of $F_n$, we have

$$(n - 1)^{P_n} \leq \prod_{p \text{ prim. div. of } F_n} p \mid F_n \leq \alpha^{n-1} ,$$

where $\alpha := (1 + \sqrt{5})/2$, and consequently

$$P_n \leq \frac{(n - 1)\log \alpha}{\log (n - 1)} .$$

Is some better upper bound known?

[1] Bilu, Hanrot, and Voutier, Existence of primitive divisors of Lucas and Lehmer numbers, Journal für die reine und angewandte Mathematik (Crelles Journal), 2001(539), pp. 75-122.

• You can get a tiny improvement by noting that if $p_1,\ldots,p_k$ are the primitive divisors in increasing order, then first (as you note) $p_1\ge n-1$, and then $p_2\ge p_1+2=n+1$, etc. So $(n-1)(n+1)\cdots(n+2k-3)\le\alpha^{n-1}$. – Joe Silverman Apr 21 '17 at 13:15
• @JoeSilverman, do we know that primitive divisors occur with low multiplicity? Otherwise a large prime power could be a factor. On a brighter note, Granville showed that for some sequences, primitive divisors occur to an odd power for n not too small. Gerhard "Can't Be Good Without Bad" Paseman, 2017.04.21. – Gerhard Paseman Apr 21 '17 at 16:42
• Also, if n itself has a small prime factor k, then you can reduce the exponent (n-1) by subtracting something near n/k. This is significant for n which are not coprime to 6. (Maybe even replace the right hand side by $\alpha^{\phi(n)}$.) Gerhard "Use Primitive Facts For Optimization" Paseman, 2017.04.21. – Gerhard Paseman Apr 21 '17 at 16:50
• @GerhardPaseman As far as I know, there are no significant theorems saying that most primitive divisors appear with low multiplicity, although in practice that's surely the case. I think that in general, for questions of this sort, it's best to first consider the simpler case of the sequence $2^n-1$, or $A^n-1$. And just the fact we don't know that $2^p-1\not\equiv0\pmod{p^2}$ for infinitely many primes indicates our lack of understanding for these sorts of questions. The OP might have better luck with an average question, i.e., bound growth of $\sum_{n<X}P_n$. – Joe Silverman Apr 21 '17 at 18:45

A known bound for the average $\frac{1}{x}\sum_{n\leq x}P_n$ is $$\limsup_{x\rightarrow\infty} \frac{\log x}{x^2} \sum_{n\leq x}P_n \leq \frac{3}{2 \pi^2} \log \alpha.$$ This is not much better than the above point-wise bound. Making progress on this average seems to be hard. One could try to get some sort of prime number theorem $$\sum_{n\leq x}P_n \sim \,\,\,?$$ The main obstacle here seems to be that all proofs of the prime number theorem (at least the ones I know) somehow rely on $$\sum_{p\leq x}\log p \sim \sum_{n\leq x} \Lambda(n)$$ with $\Lambda$ denoting the von Mangoldt function. In our situation we can determine the asymptotic behavior of the following sums $$\sum_{p: p|F_i \text{ for some } i\leq x} e_p\log p \sim \sum_{n: n|F_i \text{ for some } i\leq x} \Lambda(n)$$ where the sums are taken over (prime) divisors of Fibonacci numbers and $e_p$ denotes the largest exponent such that whenever $p|F_i\Rightarrow p^{e_p}|F_i$. The hard part is now, to relate this asymptotic behavior to that of $$\sum_{p: p|F_i \text{ for some } i\leq x} \log p$$ a weighted version of the sum we are interested in. It is not clear how this can be done. For the averages of this weighted version it is known that
$$\limsup_{x\rightarrow\infty} \frac{1}{x^2} \sum_{p|F_i\text{ for some } i\leq x} \log p \leq \frac{3}{ \pi^2} \log \alpha.$$ We also know that any improvement on the constant here would imply the existence of infinitely many Wall-Sun-Sun primes. It is an open problem whether such primes exist. However, since partial summation works differently here, the relation of the weighted average to the average is not obvious.