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.
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}&lt;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
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}&lt;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