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.

  • $\begingroup$ 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}$. $\endgroup$ – Joe Silverman Apr 21 '17 at 13:15
  • $\begingroup$ @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. $\endgroup$ – Gerhard Paseman Apr 21 '17 at 16:42
  • $\begingroup$ 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. $\endgroup$ – Gerhard Paseman Apr 21 '17 at 16:50
  • $\begingroup$ @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$. $\endgroup$ – 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.

  • $\begingroup$ Thanks. Would you kindly give me the reference of the first result? $\endgroup$ – user40023 Apr 26 '17 at 11:22
  • $\begingroup$ Sure. E.g. Thm. 7 in this paper. $\endgroup$ – Uwe Stroinski Apr 26 '17 at 17:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy