The Fibonacci sequence modulo $5^n$

Question

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.

Answer 1

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$.

Answer 2

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.