16
$\begingroup$

The first few powers of $5$ are given by:

\begin{array}{r} 5 \\ 25 \\ 125 \\ 625 \\ 3125 \\ 15625\\ 78125\\ 390625\\ 1953125\\ 9765625\\ 48828125\\ 244140625\\ 1220703125\\ 6103515625\\ \end{array}

We can see that the last digit is always $5$ and the second to last digit is always $2$. The preceding digit cycles between $1$ and $6$, and the one before that between $3,5,8$ and $0$. We can continue:

\begin{array}{ll} \text{digit} & \text{period} \\ 1 & 5\\ 2 & 2\\ 3 & 16\\ 4 & 3580\\ 5 & 17956240\\ 6 & 3978175584236200 \end{array}

Apart from the first 2 $(5$ and $2)$ we see that all these periods appear to be congruent to 7 modulo 9.

Can this be proven?

$\endgroup$
11
  • 3
    $\begingroup$ Note that you're using "period" in a sense that most mathematicians don't use it. You are concatenating the digits that appear in the repeating sequence - usually "period" refers to the length of the repeating sequence ... $\endgroup$ Dec 31, 2014 at 12:17
  • 1
    $\begingroup$ @ZubinMukerjee: Thanks for explaining that, I was wondering about it for a while now. $\endgroup$ Dec 31, 2014 at 12:17
  • 2
    $\begingroup$ @ZubinMukerjee: this follows from the fact that the period of $5^i$ modulo $10^k$ (hence $2^k$) equals $2^{k-2}$. This can be proven by noting that$$ 5^{2^t}-1=(5^{2^{t-1}}+1)(5^{2^{t-2}}+1)\cdots(5^2+1)(5+1)(5-1) $$ contains exactly $\underbrace{1+1+\cdots+1}_t+2=t+2$ prime factors $2$. $\endgroup$
    – user133281
    Dec 31, 2014 at 12:47
  • 1
    $\begingroup$ @barakmanos How so? $\endgroup$ Dec 31, 2014 at 13:02
  • 3
    $\begingroup$ Claim: Let $s_n$ be the sum of the digits in the $n$-th digit "period". Then for $n\ge3$, $s_n$ obeys the recursive relationship $$s_{n+1}=2s_n+2.$$ This works for the reported first $7$ reported "periods". Additionally, this would prove the question by an easy inductive argument. $\endgroup$ Dec 31, 2014 at 13:07

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Wow, thanks! But where does the "(since it must also divide $2^{k−1}$)" come from in showing that the order of $5$ is $2^{k-2}$? $\endgroup$ Jan 2, 2015 at 0:02
  • $\begingroup$ @WardBeullens By Lagrange's Theorem because the order of $\mathbb{Z}/2^k\mathbb{Z}^\times$ is $2^{k-1}$. $\endgroup$
    – Zander
    Jan 2, 2015 at 0:09
  • $\begingroup$ off course, thanks! $\endgroup$ Jan 2, 2015 at 0:14

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .