# How many times can $p$ divide $F_n$?

Given a prime $p$ and a number $n$ (or perhaps just an upper bound $x$ with some unknown $n\le x$), trivially one has $$\operatorname{ord}_p F_n\le\frac{\log F_n}{\log p}\approx\frac{n\log\varphi}{\log p}$$ where $F_n$ is the n-th Fibonacci number and $\operatorname{ord}_qm$ is the greatest $k$ such that $q^k|m.$ I'm looking for a less trivial bound, any suggestions?

It seems that $$\operatorname{ord}_p F_n\stackrel{?}{\le}2+\frac{\log(n/3)}{\log 2}$$ which I believe governs $\operatorname{ord}_2F_n.$ I don't have a proof but this is probably not hard to show. On the other hand I have no idea how to show that this works for all primes $p$, even though they 'should' be smaller.

Since the Fibonacci numbers grow exponentially, it's hard to work with numbers as big as $F_n$ directly, and probably $p^{\operatorname{ord}_pF_n}$ is much smaller than $F_n$. I saw sequence A135939 in the OEIS which unfortunately doesn't have useful information that I could see.

• For odd prime $p$, the critical cases are when $n=p^kn_p$ where $F(n_p)$is the least positive $F(x)$ divisible by $p$, because $F(p^kn_p)$ is the least positive $F(x)$ divisible by $p^{k+k_0}$,where $k_0=ord_pF(n_p).$ (Also $n_p$ is a divisor of $p+1$ or of $p-1$ for $p\ne 5.)$ It is conjectured that $k_0=1$. It is not known that $k_0\leq 2$ but if it is true then your conjecture is easily proven. I can't estimate the degree of difficulty of your Q. Commented Nov 16, 2015 at 15:52

The Fibonacci entry point $n_p$ is the least number with $p|F_{n_p}.$ Unless $p$ is a Wall-Sun-Sun prime, $p^2$ does not divide $F_{n_p}$. $n_p\le p+1,$ with $p$ dividing either $p+1$ or $p-1$ unless $p=5$.

There are four cases to consider. If $p=2$ then either $\operatorname{ord}_2(F_n)\le3$ unless $12|n$ in which case $$\operatorname{ord}_2(F_n)=2+\operatorname{ord}_2(n)\le2+\frac{\log(n/3)}{\log2}$$ (see [1] for details). Checking up to 6 verifies that this bound holds for all $n$.

If $p=5$ then $$\operatorname{ord}_5(F_n)=\operatorname{ord}_5(n)\le\frac{\log n}{\log 5}.$$

Aside from these special cases, $\operatorname{ord}_p(F_n)$ is 0 if $n_p\not|n$ and $\operatorname{ord}_p(n\cdot F_{n_p})$ otherwise, see section 3 in [1]. This forms the basis for the remaining steps.

If $p$ is a Wall-Sun-Sun prime then at worst $F_{n_p}=p^e$ for some $e$. Since $n_p\le p+1,$ $$\operatorname{ord}_p(F_p)\le \frac{\log F_{p+1}}{\log p}+\frac{\log\left(n/(p+1)\right)}{\log p}\sim\frac{\log n}{\log p}.$$

In the non-Wall-Sun-Sun case ($p\not\in\{2,5\}$), we can do better. A number $n\le x$ could be, in the worst case, $n_pp^e$ with $F_{n_p}=p$ so that $\operatorname{ord}_p(F_p)=1+e,$ yielding $$\operatorname{ord}_p(F_p)\le1+\frac{\log\left(\frac{n}{\operatorname{round}\left(\frac{\log(p\sqrt5)}{\log\varphi}\right)}\right)}{\log p}<1+\frac{\log n-\log(2\log p)}{\log p}.$$

There are no Wall-Sun-Sun primes less than $1.5\times10^{17}.$ [2] This means that unless $x$ is larger, you can use the better bound.

[1] T. Lengyel, The order of the Fibonacci and Lucas numbers (1993)

[2] PrimeGrid PRPNet, Wall-Sun-Sun Prime Search

[3] N. J. A. Sloane, Sequence A001177 in the OEIS

[4] N. J. A. Sloane, Sequence A001602 in the OEIS

[5] Labos Elemer and Ralf Stephan, Sequence A090740 in the OEIS