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$ – Zubin Mukerjee Dec 31 '14 at 12:17
  • 1
    $\begingroup$ @ZubinMukerjee: Thanks for explaining that, I was wondering about it for a while now. $\endgroup$ – Raskolnikov Dec 31 '14 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 '14 at 12:47
  • 1
    $\begingroup$ @barakmanos How so? $\endgroup$ – Ward Beullens Dec 31 '14 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$ – Peter Woolfitt Dec 31 '14 at 13:07
1
$\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$ – Ward Beullens Jan 2 '15 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 '15 at 0:09
  • $\begingroup$ off course, thanks! $\endgroup$ – Ward Beullens Jan 2 '15 at 0:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.