Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

If you add the decimal digits of multiples of 9,possibly repeatedly, you get 9. For instance, with 18 we have $$18\mapsto 1+8=9$$ and with 909 we have $$ 909\mapsto 9+0+9=18\mapsto 1+8=9.$$ This is proven.

If you do the same with powers of two, you develop a repeating pattern, 1,2,4,8,7,5, even when you descend negative powers. I don't know if this stops eventually, but it seems like there might be a proof for it. Can anyone prove this?

\begin{align*} .0625\mapsto 6+2+5=13&\mapsto 4 \\ .125&\mapsto 8 \\ .25 &\mapsto 7 \\ .5 &\mapsto 5 \\ 1&\mapsto 1 \\ 2 &\mapsto 2 \\ 4 &\mapsto 4 \\ 8&\mapsto 8 \\ 16&\mapsto 7 \\ 32&\mapsto 5 \\ 64\mapsto 10 &\mapsto 1 \\ 128&\mapsto 2 \\ 256 \mapsto 13 &\mapsto 4 \\ 512 &\mapsto 8 \\ 1024 &\mapsto 7 \\ 2048 \mapsto 14&\mapsto 5 \\ 4096\mapsto 19 &\mapsto 1 \\ \end{align*}

share|improve this question

1 Answer 1

We look at $2^n$, where $n$ ranges over the non-negative integers.

The key is the fact that $2^6$ has remainder $1$ on division by $9$. Using congruence notation, we have $2^6\equiv 1\pmod{9}$. Let $n$ be any non-negative integer. We can express $n$ as $6q+r$, where $0\le r\le 5$ ($q$ stands for quotient, $r$ for remainder).

It follows that $$2^n=2^{6q+r}=(2^6)^q 2^r\equiv (1)^q 2^r\equiv 2^r\pmod{9}.$$ So the remainder when you divide $2^n$ by $9$ depends only on $r$. For $r=0$, $1$, $2$, $3$, $4$, and $5$, these remainders are, as you observed, $1$, $2$, $4$, $8$, $7$, and $5$.

To connect this with sums of (decimal) digits, observe that a decimal number like $6852$ is just $(6)(10^3)+(8)(10^2)+(5)(10^1) +(2)(10^0)$. But for any non-negative integer $k$, we have $10^k\equiv 1\pmod{9}$. So $6852\equiv 6+8+5+2 \pmod{9}$. Thus the remainder when $6852$ is divided by $9$ is the same as the remainder when $6+8+5+2$ is divided by $9$. Asimilar remark holds for any non-negative integer expressed in decimal form.

Since remainders when $2^n$ is divided by $9$ cycle with period $6$, and the "casting out nines" process gives us these remainders, the pattern you observed continues forever.

You extended the pattern to negative exponents. This is an interesting observation that I do not recall seeing before. Express $2^{-n}$ as a decimal, by noting that $$2^{-n}=\frac{1}{2^n}=\frac{5^n}{10^n}.$$ Then (essentially) you looked at the digit sum (modulo $9$) of $5^n$. Modulo $9$, the numbers $5^n$ cycle with period $6$, for the same reason as with $2^n$.

Now calculate $5^n$ modulo $9$, for $n=0,1, 2, 3, 4, 5$. We get that $5^n$ is congruent in turn to $1$, $5$, $7$, $8$, $4$, and $2$ modulo $9$. So the pattern does indeed continue "backwards."

Remark: For a more general approach, please see Euler's Theorem.

share|improve this answer
    
You don't actually need to compute the same thing for $5^n$. Just note that 2 and 5 are inverses mod 9. –  ronno Aug 21 '12 at 7:30
    
Thanks for the comment. I was dissatisfied with my answer, still am, was and am uncertain about appropriate level. –  André Nicolas Aug 21 '12 at 8:39

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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