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](https://en.wikipedia.org/wiki/Pisano_period).


It [is known](https://en.wikipedia.org/wiki/Pisano_period) 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.



The Fibonacci sequence modulo $5^n$
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$.


