The Fibonacci sequence modulo $5^n$ Let $(F_k)_{k=0}^\infty$ be the classical Fibonacci sequence, defined by the recursive formula $F_{k+1}=F_k+F_{k-1}$ where $F_0=0$ and $F_1=1$.
For every $n\in\mathbb N$ let $\pi(n)$ be the smallest positive number such that $$\begin{cases}
F_{\pi(n)}=F_0 \mod n,\\
F_{\pi(n)+1}= F_1\mod n.
\end{cases}$$ The number $\pi(n)$ is called the $n$-th Pisano period.
It is known that $\pi(5^n)=4\cdot 5^n$ for every $n\in\mathbb N$.
Definition. A number $n\in\mathbb N$ is called Fibonacci uniform if $n$ divides $\pi(n)$ and for every $a\in \{1,\dots,n\}$ the set $\{k\in\{1,\dots,\pi(n)\}:F_k=a\mod n\}$ has cardinality $\pi(n)/n$.
Example. The number $n=5$ is Fibonacci uniform which is witnessed by the first $20=\pi(5)$ Fibonacci numbers modulo 5:
$$\mbox{0 1 1 2 3 0 3 3 1 4 0 4 4 3 2 0 2 2 4 1.}$$
On the other hand, the number $n=6$ is not Fibonacci uniform since among the  first $24=\pi(6)$ Fibonacci numbers (modulo 6)
$$\mbox{0 1 1 2 3 5 2 1 3 4 1 5 0 5 5 4 3 1 4 5 3 2 5 1}$$
0 appears 2 times; 1: 6 times; 2: 3 times; 3: 4 times; 4: 3 times;  5:  6 times.
It can be shown that each Fibonacci uniform number is a power of 5. Computer calculations show that for $n\le 10$ the power $5^n$ is indeed Fibonacci uniform. This suggests the following

Conjecture. For every $n\in\mathbb N$ the number $5^n$ is Fibonacci uniform, which means that for every $a\in\{1,\dots,5^n\}$ the set $\{k\in\{1,\dots,4\cdot 5^n\}:F_k=a\mod 5^n\}$ contains exactly 4 numbers.

Now the question how to prove this conjecture.
 A: I claim that for even $n\in \{0,2,4,\ldots, 4\cdot 5^n-2\}$ each remainder of $F_n$ modulo $5^n$ is realized at most twice (thus exactly twice), and the same for odd $n\in \{1,3,5,\ldots, 4\cdot 5^n-1\}$. Denoting $u=(1+\sqrt{5})/2$, $v=(1-\sqrt{5})/2$ we have Binet formula $F_n=(u^n-v^n)/(u-v)$. If $k,m$ are even, then $$F_k-F_m=\frac{u^k-u^{-k}-u^m+u^{-m}}{u-v}=\frac{(u^k-u^m)(1+u^{-k-m})}{u+1/u}.$$
Let us look at powers of $u$ modulo powers of 5. I claim that $u^2$ is congruent to -1, and $u^4$ is congruent to 1 modulo $\sqrt{5}$, and this is lifted by standard argument to
$u^{2\cdot 5^s}$ congruent to $-1$; $u^{4\cdot 5^s}$ congruent to $1$ modulo $5^{s}$ but not modulo $5^{s+1}$;  for $s\geqslant 1$.
Therefore $F_k-F_m$ is divisible by $5^n$ if and only if $k=m$ or $k+m\equiv 2\cdot 5^n \pmod {4\cdot 5^n}$.
If $k,m$ are odd, then $$F_k-F_m=\frac{u^k+u^{-k}-u^m-u^{-m}}{u-v}=\frac{(u^k-u^m)(1-u^{-k-m})}{u+1/u}.$$ This is divisible by $5^n$ if and only if $k=m$ or $k+m$ is divisible by $4\cdot 5^n$.
A: Fedor Petrov gave a satisfactory answer, but here is another one, based on a linear algebraic reasoning.

The following is a general fact, which proof is left as an exercise.
Lemma: Let $C$ be a $\mathbb{Z}$-valued matrix and fix a prime $p\geq 5$.
If $C^2=0$ over $\mathbb{F}_p$ then for every natural $m$, $(I+C)^m=I+mC$
over the ring $\mathbb{Z}/p^{\nu_p(m)+1}$.
Here $\mathbb{F}_p$ denotes the field with $p$ elements and
$\nu_p(m)$ denotes the
$p$-adic valuation of $m$.
My goal is to explain how the following claim, which clearly implies the OP's conjecture, is implied by the above lemma.
Cliam: For every $i=1,\ldots 4$ and every natural $n$, the map $\pi:\mathbb{Z}\to \mathbb{Z}/5^n\mathbb{Z}$ forms a bijection when restricted to the set $S=\{F_{4k+i}\mid k=0,\dots,5^n-1\}$.
Recall that the Fibonacci sequence could be computed by
$
\begin{bmatrix}
F_{k+1} \\
F_{k} 
\end{bmatrix}
=
A^k
\begin{bmatrix}
1 \\
0 
\end{bmatrix}
$,
where $A=\begin{bmatrix}
1 & 1 \\
1 & 0
\end{bmatrix}$.
Note that over $\mathbb{F}_5$, 3 is the unique eigenvalue of the matrix $A$, and its eigenspace $E$ is the span of $\begin{bmatrix}
3 \\
1
\end{bmatrix}$.
The "moral" reason for the period 4 appearing in the claim is that 3 is a 4th root of unity in $\mathbb{F}_5$.
Thus the $\mathbb{Z}$-valued matrix $B=A^4$, becomes unipotent over $\mathbb{F}_5$: 1 is its unique eigenvalue, with eigenspace $E$. We get that over $\mathbb{F}_5$, $E$ is both the image and the kernel of $C=B-I$
and in particular, $C^2=0$.
We can now prove the claim.
Clearly it is enough to show that $\pi$ is injective on $S$:
for every $0\leq k<k+m\leq 5^n-1$,
$F_{4(k+m)+i}-F_{4k+i}\neq 0$ over $\mathbb{Z}/5^n$.
In fact, we will show that it does not vanish over the quotient ring $\mathbb{Z}/5^{\nu_5(m)+1}$.
Over the latter ring we have by the lemma that
$$\begin{bmatrix}
F_{4(k+m)+i+1}-F_{4k+i+1} \\
F_{4(k+m)+i}-F_{4k+i}
\end{bmatrix}
= (B^m-I)\begin{bmatrix}
F_{4k+i+1} \\
F_{4k+i}
\end{bmatrix}=
mC\begin{bmatrix}
F_{4k+i+1} \\
F_{4k+i}
\end{bmatrix},$$
so it is enough to show that the second coordinate of $u=C\begin{bmatrix}
F_{4k+i+1} \\
F_{4k+i}
\end{bmatrix}$ is invertible, as $m\neq 0$.
Thus, we need to show that the second coordinate of $u$ does not vanish over $\mathbb{F}_5$.
Working over $\mathbb{F}_5$, we have that $u$ is in the image of $C$, that is $E$, thus proportional to $\begin{bmatrix}
3 \\
1
\end{bmatrix}$.
In particular, its second coordinate vanishes iff $u=0$,
equivalently, if $\begin{bmatrix}
F_{4k+i+1} \\
F_{4k+i}
\end{bmatrix}$ is in the kernel of $C$, that is $E$.
But $E$ is $A^{-1}$ invariant and it does not contain $\begin{bmatrix}
1 \\
0
\end{bmatrix}$, so it does not contain $\begin{bmatrix}
F_{4k+i+1} \\
F_{4k+i}
\end{bmatrix}=A^{4k+1}\begin{bmatrix}
1 \\
0
\end{bmatrix}$ either. This finishes the proof.
