pattern in decimal representation of powers of 5

Solution 1:

Write $a\%n$ for the least non-negative integer congruent to $a$ modulo $n$, i.e. $a\%n=r$ iff $a\equiv r\pmod{n}$ and $0\le r<n$. In particular, $a\% 10^k$ is the number represented by the last $k$ digits of $a$.

Note that the cycle of the last four digits contains $625,3125,5625,8125$, which are $1,5,9,13$ times $5^4$. Similarly the cycle of the last five digits contains $$ \begin{array}{ll} 3125 = 1\times 5^5 & 53125 = 17\times 5^5 \\ 15625 = 5\times 5^5 & 65625 = 21\times 5^5 \\ 28125 = 9\times 5^5 & 78125 = 25\times 5^5 \\ 40625 = 13\times 5^5 & 90625 = 29\times 5^5 \end{array} $$

In general, these cycles have the following properties for $k>1$:

P1: $5^n\%10^k$ repeats in a cycle of length $2^{k-2}$ for $n\ge k$.

P2: These sets, which we will denote by $S_k$, are the same, formalizing the pattern alluded to above: $$S_k = \left\{5^n\% 10^k\right\}_{n=k}^{k+2^{k-2}-1} = \left\{(4n+1)5^k\right\}_{n=0}^{2^{k-2}-1}$$

Let $$A_k = \sum_{x\in S_k} x \\ B_k = \sum_{x\in S_k} \left\lfloor \frac{x}{10^{k-1}}\right\rfloor = \sum_{x\in S_k} \frac{x - (x\%10^{k-1})}{10^{k-1}} $$ Then $B_k$ is the sum of the digits in the number called the "period" in the question, which is congruent to the number modulo $9$.

From P1, for $k>2$ one cycle of the last $k$ digits contains two cycles of the last $k-1$ digits, so $$ A_k = 10^{k-1} B_k + 2 A_{k-1} \\ B_k \equiv A_k-2A_{k-1} \pmod {9} $$ that is, we can break down $A_k$ into two sums of the last $k-1$ digits and a sum of the first digits times $10^{k-1}$.

From P2 we can evaluate $A_k$: $$ \begin{align} A_k & = \sum_{n=0}^{2^{k-2}-1}(4n+1)5^k \\ & = 5^k\left[ \left(4\sum_{n=1}^{2^{k-2}-1} n\right) + \sum_{n=0}^{2^{k-2}-1} 1 \right] \\ & = 5^k\left(4 \frac{2^{k-2}(2^{k-2}-1)}{2} + 2^{k-2}\right) \\ & = 25\cdot 10^{k-2} \left(2^{k-1}-1\right) \\ & \equiv 7 \left(2^{k-1}-1\right) \pmod{9} \end{align} $$ from which it follows that $$ \begin{align} B_k & \equiv A_k-2A_{k-1} \\ & \equiv 7 (2^{k-1}-1) - 2\cdot 7(2^{k-2}-1) \\ & \equiv 7 \pmod {9} \end{align} $$ establishing the desired result.

Now to fill in the blanks we'll prove P1 and P2.

First $2^n\not\mid n!$. The power of $2$ in $n!$ is $v_2(n!)=\lfloor n/2\rfloor + \lfloor n/4 \rfloor + \lfloor n/8 \rfloor + \cdots<n$ (see e.g. this).

Hence $$2^n \left\vert \binom{2^n}{i} 2^i \right. = \frac{2^n C}{i!} 2^{i} $$ for some $C\in \mathbb{Z}$. Then using the binomial theorem $$ 5^{2^{k-3}} = (1+4)^{2^{k-3}} = 1+2^{k-3}\cdot 4 + \sum_{i=2}^{2^{k-3}}\binom{2^{k-3}}{i} 4^i \equiv 2^{k-1}+1 \pmod {2^k} \\ 5^{2^{k-2}} = (1+4)^{2^{k-2}} = 1 + \sum_{i=1}^{2^{k-2}}\binom{2^{k-2}}{i} 4^i \equiv 1 \pmod {2^k} $$ which establishes that the order of $5$ in $\mathbb{Z}/2^k\mathbb{Z}^{\times}$ is $2^{k-2}$ (since it must also divide $2^{k-1}$).

Hence for $1<k\le n < k+2^{k-2}$, we always have $5^n\%5^k=0$, and $5^n\%2^k$ takes on exactly $2^{k-2}$ distinct values; by the Chinese Remainder Theorem $5^n\%10^k$ also takes on exactly $2^{k-2}$ distinct values. This establishes P1.

Furthermore for $1<k\le n < k+2^{k-2}$ every $5^n\equiv (4j+1)5^k\pmod{10^k}$ for some $j$, and there are exactly $2^{k-2}$ such possibilities, so every one must occur for exactly one choice of $n$ in this range. This establishes P2.