What's the necessary and sufficient condition of $p^m|F_n$?

Question

Let {$F_n$} be Fibonacci Series defined by $F_{n+2}=F_{n+1}+F_n$ with $F_1=F_2=1$.I have proved that $3^m|F_n \Leftrightarrow 4\cdot 3^{m-1}|n$ for another problem.Then I began to think about the necessary and sufficient condition of $p^m|F_n$,where $p$ is a prime number and $m$ is a positive integer.By analyzing the first sixty terms of {$F_n$},I suppose that

where $\tau (p)$ is the least positive integer s.t. $p|F_{\tau(p)}$.

I think we could prove this with induction through several steps:

①Prove that $(F_m,F_n)=F_{(m,n)}$,where $(a,b)$ is the greastest common divisor of $a$ and $b$.

②Strengthen the proposition by proving $p^m||F_{\tau (p) \cdot p^{m-1}}$ $\ (m \geqslant 3 \ $when $p=2)$.

③Prove the proposition when $p=2$.

④Prove $p||F_{\tau (p)}$.

⑤Prove that $p^{m+1}|F_n \Leftrightarrow \tau (p) \cdot p^m|n $ ,and that $p^{m+1}||F_{\tau (p) \cdot p^m}$ ,when $p^{m}|F_n \Leftrightarrow \tau (p) \cdot p^{m-1}|n $ ,and $p^{m}||F_{\tau (p) \cdot p^{m-1}}$$\ \ $ for all odd primes $p$.

For ①,it's easy to prove $(F_n,F_{n+1})=1$ with the fact that $(F_1,F_2)=1$.And we have $$\begin{align}F_m&=F_{m-1}+F_{m-2}=F_2F_{m-1}+F_1F_{m-2}=F_2(F_{m-2}+F_{m-3})+F_1F_{m-2}\\&=(F_2+F_1)F_{m-2}+F_2F_{m-3}=F_3F_{m-2}+F_2F_{m-2}\\&=\cdots\\&=F_nF_{m-n+1}+F_{n-1}F_{m-n}\end{align}$$ when $m>n$.Thus we have $(F_m,F_n)=(F_{m-n},F_n)$ when $m>n$.So by Euclid algotithm,we have $(F_m,F_n)=F_{(m,n)}$.

For ③,it's easy to prove that $2|F_n\Leftrightarrow3|n\ $,$4|F_n\Leftrightarrow6|n\ $,$8|F_n\Leftrightarrow6|n\ $,and $8||F_6$.When $2^m|F_n\Leftrightarrow3\cdot2^{m-2}|n$ and $2^{m}||F_{3\cdot2^{m-1}}$ $(m>2)$,we have $$\begin{align}\frac{F_{3\cdot2^{m-1}}}{F_{3\cdot2^{m-2}}}&=\frac{(\frac{1+\sqrt{5}}{2})^{3\cdot2^{m-1}}-(\frac{1-\sqrt{5}}{2})^{3\cdot2^{m-1}}}{(\frac{1+\sqrt{5}}{2})^{3\cdot2^{m-2}}-(\frac{1-\sqrt{5}}{2})^{3\cdot2^{m-2}}}=(\frac{1+\sqrt{5}}{2})^{3\cdot2^{m-2}}+(\frac{1-\sqrt{5}}{2})^{3\cdot2^{m-2}}.\end{align}$$ Let {$Z_n$} be a sequence where $Z_1=1$,$Z_2=3$ and $Z_{n+2}=Z_{n+1}+Z_{n}$.Then we have $Z_n=(\frac{1+\sqrt{5}}{2})^n+(\frac{1-\sqrt{5}}{2})^n$,and $$\begin{align}&Z_1\equiv1,Z_2\equiv1,Z_3\equiv0,Z_4\equiv1,Z_5\equiv1,Z_6\equiv0,\cdots(mod2)\\ &Z_1\equiv1,Z_2\equiv3,Z_3\equiv0,Z_4\equiv3,Z_5\equiv3,Z_6\equiv2,Z_7\equiv1,Z_8\equiv3,\cdots(mod4) \end{align}$$ which tolds us that if $6|n$,then $2||Z_n$.So we have $$\begin{align}2||Z_{3\cdot2^{m-2}}=\frac{F_{3\cdot2^{m-1}}}{F_{3\cdot2^{m-2}}}.\end{align}$$ And $2^{m}||F_{3\cdot2^{m-1}}\ \ $,thus $2^{m+1}||F_{3\cdot2^{m}}$.Obviously,the multiple of $2^{m+1}$ is the multiple of $2^{m}$.So if $2^{m+1}|F_n$,then $2^{m}|F_n$.So we have $3\cdot2^{m-2}|n$.Let $n=3k\cdot2^{m-2}$,where k is a positive integer.Then with ①,we have $(F_{3\cdot2^{m-1}}\ ,\ F_{3k\cdot2^{m-2}}\ )=F_{3\cdot2^{m-2}\ \ (2,k)}$.If $2\nmid k$,then $(F_{3\cdot2^{m-1}}\ ,\ F_{3k\cdot2^{m-2}}\ )=F_{3\cdot2^{m-2}}\ \ $,which means $2^m||F_{3k\cdot2^{m-2}}\ \ $;if $2|k$,then $(F_{3\cdot2^{m-1}}\ ,\ F_{3k\cdot2^{m-2}}\ )=F_{3\cdot2^{m-1}}\ \ $,which means $2^{m+1}|F_{3k\cdot2^{m-2}}\ \ $.So $2^{m+1}|F_n\Leftrightarrow3\cdot2^{m-1}|n$.By the induction principle,we've achieved ③.

For ⑤,similar to ③,we have only to prove $p^{m+1}||F_{\tau (p)\cdot p^{m}}$ ,when $p^{m}|F_n \Leftrightarrow \tau (p) \cdot p^{m-1}|n $ ,and $p^{m}||F_{\tau (p) \cdot p^{m-1}}\ $.But actually I can only do this when $p$ is a certain prime such as $3,5$.I can't find a way to prove it for a general $p\ $(constructing a sequence is not suitable to an odd prime ,or my poor knowledge of sequence can't support me to step further).When $p=3$,I proved it like that:

It's easy to know $\tau (3)=4$.And it's also easy to prove that $3|F_n\Leftrightarrow4|n$,and $3||F_4$.If $3^{m}|F_n\Leftrightarrow4\cdot3^{m-1}|n$ and $3^m||F_{4\cdot3^{m-1}}\ $,then: we have $$\begin{align}\frac{F_{4\cdot3^{m}}}{F_{4\cdot3^{m-1}}}&=\frac{(\frac{1+\sqrt{5}}{2})^{4\cdot3^m}-(\frac{1-\sqrt{5}}{2})^{4\cdot3^m}}{(\frac{1+\sqrt{5}}{2})^{4\cdot3^{m-1}}-(\frac{1-\sqrt{5}}{2})^{4\cdot3^{m-1}}}=(\frac{1+\sqrt{5}}{2})^{8\cdot3^{m-1}}+(\frac{1+\sqrt{5}}{2})^{4\cdot3^{m-1}}(\frac{1-\sqrt{5}}{2})^{4\cdot3^{m-1}}+(\frac{1-\sqrt{5}}{2})^{8\cdot3^{m-1}}\\ &=\frac{(1+\sqrt{5})^{8\cdot3^{m-1}}+(-4)^{4\cdot3^{m-1}}+(1-\sqrt{5})^{8\cdot3^{m-1}}}{2^{8\cdot3^{m-1}}}=\frac{2\sum_{t=0}^{4\cdot3^{m-1}}{{{8\cdot3^{m-1}\ }\choose{2t}}\cdot5^t}+4^{4\cdot3^{m-1}}}{2^{8\cdot3^{m-1}}}. \end{align}$$ And because $$\begin{align}2\sum_{t=0}^{4\cdot3^{m-1}}{{{8\cdot3^{m-1}\ }\choose{2t}}\cdot5^t}+4^{4\cdot3^{m-1}}&\equiv 2\sum_{t=0}^{2\cdot3^{m-1}}{{{8\cdot3^{m-1}\ }\choose{4t}}}+2\sum_{t=0}^{2\cdot3^{m-1}}{{{8\cdot3^{m-1}\ }\choose{4t+2}}\cdot2}+1\\&\equiv 2\sum_{t=0}^{4\cdot3^{m-1}}{{{8\cdot3^{m-1}\ }\choose{2t}}}+2\sum_{t=0}^{2\cdot3^{m-1}}{{{8\cdot3^{m-1}\ }\choose{4t+2}}}+1\\&\equiv 2^{8\cdot3^{m-1}}+2^{8\cdot3^{m-1}-1}-2^{4\cdot3^{m-1}}+1\\&\equiv 1+2-1+1 \equiv 0 (mod3) \end{align}$$ and it's easy to prove that $2\sum_{t=0}^{4\cdot3^{m-1}}{{{8\cdot3^{m-1}\ }\choose{2t}}\cdot5^t}+4^{4\cdot3^{m-1}}\equiv 3(mod9)$when $m=1$,and when $m>1$ $$\begin{align}2\sum_{t=0}^{4\cdot3^{m-1}}{{{8\cdot3^{m-1}\ }\choose{2t}}\cdot5^t}+4^{4\cdot3^{m-1}}&\equiv 2\Biggl( \sum_{t=0}^{2\cdot3^{m-1}}{\biggl( {{8\cdot3^{m-1}}\choose{2t}}\cdot5^t+{{8\cdot3^{m-1}}\choose{8\cdot3^{m-1}-2t}}\cdot5^{8\cdot3^{m-1}-2t} \biggl)}-{{8\cdot3^{m-1}}\choose{4\cdot3^{m-1}}}\cdot5^{2\cdot3^{m-1}} \Biggr)+1\end{align}$$ $$\begin{align}&\equiv 2\Biggl( \sum_{t=0}^{3^{m-2}}{\biggl( {{8\cdot3^{m-1}}\choose{12t}}+{{8\cdot3^{m-1}}\choose{8\cdot3^{m-1}-12t}} \biggl)}+\sum_{t=0}^{3^{m-2}-1}{\biggl( {{8\cdot3^{m-1}}\choose{12t+2}}\cdot5+{{8\cdot3^{m-1}}\choose{8\cdot3^{m-1}-12t-2}}\cdot2 \biggl)}\\ &\ +\sum_{t=0}^{3^{m-2}-1}{\biggl( {{8\cdot3^{m-1}}\choose{12t+4}}\cdot7+{{8\cdot3^{m-1}}\choose{8\cdot3^{m-1}-12t-4}}\cdot4 \biggl)}+\sum_{t=0}^{3^{m-2}-1}{\biggl( {{8\cdot3^{m-1}}\choose{12t+6}}\cdot8+{{8\cdot3^{m-1}}\choose{8\cdot3^{m-1}-12t-6}}\cdot8 \biggl)}\\ &\ +\sum_{t=0}^{3^{m-2}-1}{\biggl( {{8\cdot3^{m-1}}\choose{12t+8}}\cdot4+{{8\cdot3^{m-1}}\choose{8\cdot3^{m-1}-12t-8}}\cdot7 \biggl)}+\sum_{t=0}^{3^{m-2}-1}{\biggl( {{8\cdot3^{m-1}}\choose{12t+10}}\cdot2+{{8\cdot3^{m-1}}\choose{8\cdot3^{m-1}-12t-10}}\cdot5 \biggl)}-{{8\cdot3^{m-1}}\choose{4\cdot3^{m-1}}} \Biggr)+1\end{align}$$ $$\begin{align}&\equiv 2\Biggl( \sum_{t=0}^{3^{m-2}}{\biggl( {{8\cdot3^{m-1}}\choose{12t}}+{{8\cdot3^{m-1}}\choose{8\cdot3^{m-1}-12t}} \biggl)}+\sum_{t=0}^{3^{m-2}-1}{\biggl( {{8\cdot3^{m-1}}\choose{12t+2}}\cdot8+{{8\cdot3^{m-1}}\choose{8\cdot3^{m-1}-12t-2}}\cdot8 \biggl)}\\ &\ +\sum_{t=0}^{3^{m-2}-1}{\biggl( {{8\cdot3^{m-1}}\choose{12t+4}}+{{8\cdot3^{m-1}}\choose{8\cdot3^{m-1}-12t-4}} \biggl)}+\sum_{t=0}^{3^{m-2}-1}{\biggl( {{8\cdot3^{m-1}}\choose{12t+6}}\cdot8+{{8\cdot3^{m-1}}\choose{8\cdot3^{m-1}-12t-6}}\cdot8 \biggl)}\\ &\ +\sum_{t=0}^{3^{m-2}-1}{\biggl( {{8\cdot3^{m-1}}\choose{12t+8}}+{{8\cdot3^{m-1}}\choose{8\cdot3^{m-1}-12t-8}} \biggl)}+\sum_{t=0}^{3^{m-2}-1}{\biggl( {{8\cdot3^{m-1}}\choose{12t+10}}\cdot8+{{8\cdot3^{m-1}}\choose{8\cdot3^{m-1}-12t-10}}\cdot8 \biggl)}-{{8\cdot3^{m-1}}\choose{4\cdot3^{m-1}}} \Biggr)+1\end{align}$$ $$\begin{align} &\equiv 2\Biggl( \sum_{t=0}^{4\cdot3^{m-1}}{{{8\cdot3^{m-1}}\choose{2t}}}+7\sum_{t=0}^{2\cdot3^{m-1}}{{{8\cdot3^{m-1}}\choose{4t+2}}} \Biggl)+1\\ &\equiv 2(2^{8\cdot3{m-1}-1}+7(2^{8\cdot3{m-1}-2}-2^{4\cdot3{m-1}-1}))+1\\ &\equiv 2(5+7\times(7-5))+1 \equiv 3(mod9) \end{align}$$ (I'm terribly sorry for my making it so ugly,but it seems it has been beyond its limit),we have $3||\frac{F_{4\cdot3^m}}{F_{4\cdot3^{m-1}}}$,thus $3^{m+1}||F_{4\cdot3^m}$.Then $(F_{4\cdot3^m},F_{4k\cdot3^{m-1}})=F_{4\cdot3^{m-1}\ \ (3,k)}$.Similar to ③,We have $3^{m+1}|F_n \Leftrightarrow 4\cdot3^m|n$.Then by induction principle,$3^m|F_n\Leftrightarrow4\cdot3^{m-1}|n$.

But I can't work out in this way for a general $p$.

And I have no idea about ④,which is the basic of the induction.

How could I prove or disprove my suppose?Is there any theory about this?Is there a formula about $\tau (p)$?

Appreciated for any suggestion.

And I'm sorry for my possibly strange expressions and wrong grammar for I'm still an English learner.

Answer 1

You clearly put a lot of effort into writing up your question, but I hope you can understand why the sheer number of symbols you wrote is a nightmare to try to read. I will not try. Trying to prove that rule by induction using the explicit formula for Fibonacci numbers and all those binomial coefficients seems horrific to contemplate.

Here is what I consider the correct (conceptual) way to think about your question. Like you, I will use the explicit formula $$ F_n = \frac{\varphi^n - \overline{\varphi}^n}{\sqrt{5}} $$ where $\varphi = (1 + \sqrt{5})/2$ and $\overline{\varphi} = (1-\sqrt{5})/2$. Because $\varphi^2 = \varphi + 1$ and $\overline{\varphi} = 1 - \varphi$, $\varphi$ and $\overline{\varphi}$ lie in the ring $$ R = \mathbf Z[\varphi] = \mathbf Z + \mathbf Z\varphi, $$ which is analogous to the Gaussian integers $\mathbf Z[i] = \mathbf Z + \mathbf Z i$. For a prime $p$ other than $5$ (the prime $5$ is tricky because of the $\sqrt{5}$ in the denominator of the formula for $F_n$), you are seeking for each $m \geq 1$ a description of all $n \geq 1$ such that $F_n \equiv 0 \bmod p^m\mathbf Z$. Let's work not in $\mathbf Z$, but in the larger ring $R$. For congruences with ordinary integers we don't lose anything, since $$ a \equiv b \bmod M\mathbf Z \Longleftrightarrow a \equiv b \bmod MR $$ for $a, b, M \in \mathbf Z$. This is because the only fractions (rational numbers) in $R$ are ordinary integers, so $(a-b)/M$ is in $\mathbf Z$ if and only if $(a-b)/M$ is in $R$. Thanks to this equivalence, we can rewrite the condition $p^m \mid F_n$ for primes $p \not= 5$ as follows: $$ p^m \mid F_n \text{ in } \mathbf Z \Longleftrightarrow F_n \equiv 0 \bmod p^m\mathbf Z \Longleftrightarrow F_n \equiv 0 \bmod p^mR \Longleftrightarrow \frac{\varphi^n - \overline{\varphi}^n}{\sqrt{5}} \equiv 0 \bmod p^mR. $$ Since $p$ is a prime other than $5$, $\sqrt{5}$ is invertible in $R/p^mR$. Therefore $$ \frac{\varphi^n - \overline{\varphi}^n}{\sqrt{5}} \equiv 0 \bmod p^mR \Longleftrightarrow \varphi^n \equiv \overline{\varphi}^n \bmod p^mR \Longleftrightarrow \varphi^{2n} \equiv (-1)^n \bmod p^mR, $$ where I passed between the last two congruences by multiplying both sides by $\varphi$ and using the relation $\varphi\overline{\varphi} = -1$. Multiplying both sides by $(-1)^n$, we finally obtain $$ p^m \mid F_n \text{ in } \mathbf Z \Longleftrightarrow \boxed{(-\varphi^2)^n \equiv 1 \bmod p^mR}. $$ So your question is actually about computing the order of a number in modular arithmetic in $R$ modulo powers of $p$. In particular, this explains why the set of all $n \geq 1$ such that $p^m \mid F_n$ is the multiples of the least such $n$. This is a special case of a result in group theory: the powers that make something the identity in a finite group are multiples of the least such power.

The number $\varphi \bmod p^mR$ is invertible (with inverse $-\overline{\varphi} \bmod p^mR$), so it lies in the finite group of units $(R/p^mR)^\times$. Therefore there will be an $n$ such that $p^m \mid F_n$, and the smallest such $n$ is the (multiplicative) order of $-\varphi^2 \bmod p^mR$. By Lagrange's theorem from group theory, the order of an element of $(R/p^mR)^\times$ divides the size of the group $(R/p^mR)^\times$. If you know some algebraic number theory (how $p$ splits in $R$, a quadratic ring of algebraic integers), then you can compute the size of that group: $$ |(R/p^mR)^\times| = \begin{cases} (p^{m-1}(p-1))^2, & \text{ if } p \equiv 1, 4 \bmod 5, \\ p^{2(m-1)}(p^2-1), & \text{ if } p \equiv 2, 3 \bmod 5. \end{cases} $$ So your least $n$ will be a factor of this number when $p \not= 5$.

Taking $m = 1$, when you write the least $n$ such that $p \mid F_n$ as $\tau(p)$, we can say $\tau(p)$ is a factor of $$ |(R/pR)^\times| = \begin{cases} (p-1)^2, & \text{ if } p \equiv 1, 4 \bmod 5, \\ p^2-1, & \text{ if } p \equiv 2, 3 \bmod 5. \end{cases} $$ Actually, we can do a bit better: $\tau(p) \mid (p-1)$ when $p \equiv 1, 4 \bmod 5$ and $\tau(p) \mid (p+1)$ when $p \equiv 2, 3 \bmod 5$.

Case 1: $p \equiv 1, 4 \bmod 5$. Here $5$ is a square in $\mathbf Z/p\mathbf Z$, so we can make sense of $\sqrt{5}$ and thus $\varphi$ and $\overline{\varphi} = -1/\varphi$ in $\mathbf Z/p\mathbf Z$. Therefore $p \mid F_n$ is equivalent to $(-\varphi^2)^n \equiv 1 \bmod p\mathbf Z$, so the least such $n$ divides $|(\mathbf Z/p\mathbf Z)^\times|$, meaning $\tau(p) \mid (p-1)$.

Case 2: $p \equiv 2, 3 \bmod 5$. For $p=2$, $\tau(p) = 3 = p+1$ since $F_3 = 2$. Now take $p > 2$. Then $5$ is not a square in $\mathbf Z/p\mathbf Z$ but it is a square in the field $\mathbf F_{p^2}$. (This is related to $R/pR \cong \mathbf F_{p^2}$ for these $p$.) We can make sense of $\sqrt{5}$, and thus $\varphi$ and $\overline{\varphi} = -1/\varphi$, in $\mathbf F_{p^2}$. I claim $(-\varphi^2)^{p+1} = 1$ in $\mathbf F_{p^2}^\times$. The $p$th power map on $\mathbf F_{p^2}$ is the nontrivial field automorphism, so $\varphi^p = \overline{\varphi}$ in $\mathbf F_{p^2}$. Therefore in $\mathbf F_{p^2}$, $$ (-\varphi^2)^{p+1} = (-1)^{p+1}(\varphi^{p+1})^2 = (-1)^{p+1}(\overline{\varphi}\varphi)^2 = (-1)^{p+1}(-1)^2 = (-1)^{p+1}. $$ For odd $p$, $(-1)^{p+1} = 1$ since $p+1$ is even.

I don't think it is realistic to expect a formula for $\tau(p)$.

Note: The number $\tau(p)$, the least $n \geq 1$ such that $F_n \equiv 0 \bmod p$, is not the same thing as the period of the Fibonacci sequence mod $p$, which is called the $p$th Pisano period and denoted $\pi(p)$: this is the least $n \geq 1$ such that $F_n \equiv 0 \bmod p$ and $F_{n+1} \equiv 1 \bmod p$. You can have $F_n \equiv 0 \bmod p$ and $F_{n+1} \not\equiv 1 \bmod p$ sometimes. Always $\tau(p) \mid \pi(p)$. For example, $\tau(3) = 4$ while $\pi(3) = 8$, $\tau(7) = 8$ while $\pi(7) = 16$, and $\tau(13) = 7$ while $\pi(13) = 28$.

Your proposed formula for the least $n$ such that $p^m \mid F_n$ depends on your Step 4: you think the first time $p \mid F_n$ for some $n$, $p$ must divide that $F_n$ exactly once. This is the premise behind the $-1$ in the exponent of your rule $p^m \mid F_n \Longleftrightarrow \tau(p) p^{m-1} \mid n$. In similar problems about orders of numbers in modular arithmetic in $\mathbf Z$, this kind of rule often works but has counterexamples. It can happen that the first time $p$ divides a term like that, it divides it more than once.

For example, suppose you seek a formula for the decimal period of $1/p^m$, where $p$ is a prime other than $2$ or $5$ and $m \geq 1$. Call this decimal period $D(1/p^m)$. When $p = 7$, we have initially $$ D(1/7) = 6, \ D(1/49) = 6\cdot 7, \ D(1/7^3) = 6 \cdot 7^2, \ D(1/7^4) = 6 \cdot 7^3, $$ and in general $D(1/7^m) = 6 \cdot 7^{m-1} = D(1/7)7^{m-1}$ for all $m \geq 1$. When $p = 3$, we have initially $$ D(1/3) = 1, \ D(1/9) = 1, \ D(1/27) = 3, \ D(1/3^4) = 9, \ D(1/3^5) = 27, $$ and in general $D(1/3^m) = 3^{m-2} = D(1/9)3^{m-2}$ for all $m \geq 2$, and $D(1/3) = 1$. The pattern does not start at $m = 1$. It resembles your formula starting at $m=2$, and this is why the power of $3$ in the formula is $3^{m-2}$, not $3^{m-1}$.

This is closely related to orders of units in modular arithmetic: for primes $p$ not $2$ or $5$, the decimal period of $1/p^m$ is the order of $10 \bmod p^m$. We have $$D(1/p^m) = D(1/p)p^{m-1} \text{ for all } m \geq 1 $$ provided $p$ divides $10^{p-1}-1$ exactly once. This happens at $p = 7$, since $10^6 - 1 = 7(142857)$ and $7 \nmid 142857$. It does not happen at $p = 3$, since $10^{p-1} - 1 = 10^2-1 = 3^2$ is divisible by $3$ twice, not just once. In general, if $p^K$ is the highest power of $p$ dividing $10^{p-1}-1$, then $D(1/p^m) = D(1/p^K)p^{m-K}$ for all $m \geq K$, so there is a nice $p$-power pattern only starting at $m = K$.

The next prime $p$ after $3$ where $10^{p-1}-1$ is divisible by $p^2$ is $p = 487$: $$ D(1/487) = 486, \ D(1/487^2) = 486, \ D(1/487^3) = 486 \cdot 487, D(1/487^4) = 486 \cdot 487^2, $$ and in general $D(1/487^m) = 486 \cdot 487^{m-2}$ for all $m \geq 2$, but not at $m=1$. And the next prime after $487$ where $10^{p-1}-1$ is divisible by $p^2$ is $p = 56598313$: $$ D(1/p) = p-1, \ D(1/p^2) = p-1, \ D(1/p^3) = (p-1) \cdot p, $$ and in general $D(1/56598313^m) = 56598312 \cdot 56598313^{m-2}$ for $m \geq 2$.

Primes $p$ for which $p^2 \mid (10^{p-1} - 1)$ are called Wieferich primes to base $10$. Only three of them are known ($3$, $487$, and $56598313$). Standard probabilistic heuristics suggest the number of such $p \leq x$ should grow at the rate $\log \log x$, which tends to $\infty$ with $x$ , but extremely slowly. Note $\log(\log(487)) \approx 1.82 \approx 2$ and $\log(\log(56598313 )) \approx 2.88 \approx 3$. While we expect there to be infinitely many Wieferich primes to base 10, as Nick Katz once wrote "no computer experiment will ever convince us of it".

Returning to your problem, about $p^m \mid F_n$, everything hinges on how highly divisible $F_n$ is by $p$ the first time $p \mid F_n$. That is, everything depends on how highly divisible $\tau(p)$ is by $p$. If $p$ divides $\tau(p)$ just once, then your proposed formula is correct and proving it by induction is a complete nightmare that I will not think about. I prove the conjecture at the end of this post with a parameter $K$ depending on how highly divisible $F_n$ is by powers of $p$ the first time $F_n$ is divisible by $p$.

Example. Consider $3^m \mid F_n$, which is the same as $(-\varphi^2)^n \equiv 1 \bmod 3^mR$. The Fibonacci sequence begins $1, 1, 2, 3, 5, \ldots$, so the least $n$ such that $3 \mid F_n$ is $n = 4$. This says $-\varphi^2 \bmod 3R$ has order 4 in $(R/3R)^\times$, and indeed $$ (-\varphi^2)^2 = (\varphi+1)^2 = \varphi^2 + 2\varphi + 1 = 3\varphi + 2 \equiv 2 \bmod 3R, $$ so $(-\varphi^2)^4 \equiv 2^2 \equiv 1 \bmod 3R$. Since $4-1$ is divisible by $3$ exactly once, the order of $-\varphi^2 \bmod 3^mR$ is $4 \cdot 3^{m-1}$ for all $m \geq 1$.

If $p^2 \mid F_{\tau(p)}$ then your proposed formula needs to be modified in a manner analogous to the way I described for decimal periods of $1/p^k$ if $p^2 \mid (10^{p-1}-1)$. For the period $\pi(p)$ of the Fibonacci sequence modulo $p$, there is a name for primes $p$ where $p^2 \mid F_{\pi(p)}$: Wall-Sun-Sun primes. A Wikipedia page about them is here. Probabilistic heuristics suggest that there should be infinitely many Wall-Sun-Sun primes, but not a single example is known. For similar reasons, it is natural to conjecture that $p^2 \mid F_{\tau(p)}$ for infinitely many $p$, and that the set of such $p$ should be extremely sparse.

For a prime $p$ and integer $a \not= \pm 1$ such that $p \nmid a$, let $O_a(p^m)$ be the order of $a \bmod p^m$. Here are formulas expressing $O_a(p^m)$ in terms of $O_a(p)$. Note $O_a(p) \mid (p-1)$.

Case 1: $p > 2$. Let the highest power of $p$ dividing $a^{O_a(p)} - 1$ be $p^K$. Then for all $m \geq K$, $O_a(p^m) = O_a(p)p^{m-K}$. That is, $a^n \equiv 1 \bmod p^m$ if and only if $O_a(p)p^{m-K} \mid n$. In the "generic" situation, $K = 1$ (that is, $p$ divides $a^r - 1$ just once) and $O_a(p^m) = O_a(p)p^{m-1}$ for all $m \geq 1$.

Case 2: $p = 2$. If $a \equiv 1 \bmod 4$, let the highest power of $2$ dividing $a - 1$ be $2^K$, so $K \geq 2$. Then for $m \geq K$, $O_a(2^m) = 2^{m-K}$. If $a \equiv 3 \bmod 4$, let the highest power of $2$ dividing $a + 1$ be $2^K$, so $K \geq 2$. Then for $m \geq K+1$ (so starting at $m=K+1$, not at $m=K$), $O_a(2^m) = 2^{m-K}$.

To apply these order results to your Fibonacci question, we will use $p$-adic numbers and $p$-adic square roots of 5.

Theorem. If $F/\mathbf Q_p$ is unramified, $p \not= 2$, and $u \in F$ has $|u|_p = 1$ with $u$ not a root of unity, let $u \bmod p\mathcal O_F$ have order $r$ and $p^K$ for $K \geq 1$ be the highest power of $p$ dividing $u^r - 1$. Then for each $m \geq K$, the least $n \geq 1$ such that $u^n \equiv 1 \bmod p^m\mathcal O_F$ is $rp^{m-K}$.

If $F/\mathbf Q_2$ is unramified and $u \in F$ has $|u|_2 = 1$ with $u$ not a root of unity, let $u \bmod 4\mathcal O_F$ have order $r$ and $2^K$ for $K \geq 2$ be the highest power of $2$ dividing $u^r - 1$. Then for each $m \geq K$, the least $n \geq 1$ such that $u^n \equiv 1 \bmod 2^m\mathcal O_F$ is $r2^{m-K}$.

Proof. For $p \not= 2$, the $p$-adic exponential function on $p\mathcal O_F$ is an isometry, so $u^r = e^{p^Kv}$ where $|v|_p = 1$. For $m \geq 1$, if $u^n \equiv 1 \bmod p^m\mathcal O_F$ then $u^n \equiv 1 \bmod p\mathcal O_F$, so $r \mid n$. Write $n = rN$. Then $$ u^n = (u^r)^N = (e^{p^{K}v})^N = e^{p^KvN}, $$ so $$ |u^n - 1|_p = |e^{p^KvN}-1|_p = |p^KvN|_p = \frac{1}{p^K}|N|_p. $$ Therefore $$ u^n \equiv 1 \bmod p^m\mathcal O_F \Longleftrightarrow |u^n - 1|_p \leq \frac{1}{p^m} \Longleftrightarrow |N|_p \leq \frac{1}{p^{m-K}}, $$ so the least such $N$ is $p^{m-K}$ (when $m \geq K$). Therefore the least value of $n = rN$ is $rp^{m-K}$.

Now we consider $p=2$. The $2$-adic exponential function on $4\mathcal O_F$ is an isometry, so $u^r = e^{2^Kv}$ where $|v|_p = 1$. For $m \geq 2$, if $u^n \equiv 1 \bmod 2^m\mathcal O_F$ then $u^n \equiv 1 \bmod 4\mathcal O_F$, so $r \mid n$. Write $n = rN$. Then $$ u^n = (u^r)^N = (e^{2^{K}v})^N = e^{2^KvN}, $$ so $$ |u^n - 1|_2 = |e^{p^KvN}-1|_2 = |2^KvN|_2 = \frac{1}{2^K}|N|_2. $$ Therefore $$ u^n \equiv 1 \bmod 2^m\mathcal O_F \Longleftrightarrow |u^n - 1|_2 \leq \frac{1}{2^m} \Longleftrightarrow |N|_2 \leq \frac{1}{2^{m-K}}, $$ so the least such $N$ is $2^{m-K}$ (when $m \geq K$). Therefore the least value of $n = rN$ is $r2^{m-K}$.

QED

We will prove your conjecture for $p \not= 5$ by applying this theorem to $F = \mathbf Q_p(\varphi) = \mathbf Q_p(\sqrt{5})$, which is unramified for $p \not= 5$, and $u = -\varphi^2$.
For $p \not= 5$,
$$ |F_n|_p = |\varphi^n - \overline{\varphi}^n|_p = |(-\varphi^2)^n - 1|_p. $$ Therefore the least $n$ such that $p \mid F_n$ is the order of $-\varphi^2 \bmod p\mathcal O_{\mathbf Q_p(\sqrt{5})}$, so $r = \tau(p)$ when $p \not= 2, 5$.

First suppose $p \not= 2$ (so $p \not= 2$ or $5$). Let $p^K$ for $K \geq 1$ be the highest power of $p$ dividing $\tau(p)$. The theorem tells us that for each $\boxed{m \geq K}$, the least $n \geq 1$ such that $(-\varphi^2)^n \equiv 1 \bmod p^m\mathcal O_{\mathbf Q_p(\sqrt{5})}$ is $\tau(p)p^{m-K}$, so the least $n \geq 1$ such that $F_n \equiv 0 \bmod p^m$ is $\tau(p)p^{m-K}$. When $K = 1$, meaning $p$ divides $\tau(p)$ just once, we have shown for each $m \geq 1$ that the least $n \geq 1$ such that $F_n \equiv 0 \bmod p^m$ is $\tau(p)p^{m-1}$.

Next suppose $p = 2$. When is $|(-\varphi^2)^n - 1|_2 \leq 1/4$ for the first time? This is the same as $F_n$ being divisible by $4$ for the first time. The initial even Fibonacci numbers are $F_3 = 2$ and $F_6 = 8$, so the least $n$ is $n=6$. In terms of $\varphi$, $$ (-\varphi^2)^3 = -8\varphi - 5 \not\equiv 1 \bmod 4, \ \ (-\varphi^2)^6 = 144 \varphi + 89 \equiv 1 \bmod 4. $$ The highest power of $2$ dividing $(-\varphi^2)^6 - 1 = 144\varphi + 88$ is $8 = 2^3$, so $r = 6$ and $K = 3$. The theorem tells us that for each $m \geq 3$, the least $n \geq 1$ such that $(-\varphi^2)^n \equiv 1 \bmod 2^m$ is $6 \cdot 2^{m-3} = 3 \cdot 2^{m-2}$. So for $\boxed{m \geq 3}$, the least $n \geq 1$ such that $F_n \equiv 0 \bmod 2^m$ is $n = r \cdot 2^{m-K} = 3 \cdot 2^{m-2}$. We can work out the cases $m = 1$ and $2$ directly: the least $n$ such that $F_n$ is even (equivalently, $(-\varphi^2)^n \equiv 1 \bmod 2$) is $n=3$ and the least $n$ such that $F_n \equiv 0 \bmod 4$ (equivalently, $(-\varphi^2)^n \equiv 1 \bmod 4$) is $n = 6$.