Power Mad!

An excellent solution to this problem was sent in by Edward from Carre's Grammar School. Edward took a sophisticated approach and used modular arithmetic - if you are not familiar with modular arithmetic this article will help you follow his reasoning. Here is an outline of what he wrote.

(a) $2^1,\ldots,2^{99}$ can never be multiples on ten since any multiple of ten is divisible by $5$, and of course no power of $2$ is divisible by $5$.

(b) Edward provided two solutions to this part.

Method 1

We use induction. Clearly $2^1+3^1$ is divisible by $5$. Now for the induction hypothesis, suppose $2^k+3^k$ is divisible by $5$ for $k$ odd, i.e. $2^k+3^k=5m$ for some integer $m$.

Then $2^{k+2}+3^{k+2}=4\times 2^k+9\times 3^k=4(2^k+3^k)+5(3^k)=4(5m)+5(3^k)=5(4m+3^k)$ and so is divisible by $5$. This completes the induction step, and we have shown that $2^k+3^k$ is divisible by $5$ for any odd $k$.

Method 2

This method uses modular arithmetic. Edward observed the following rules:

1. If $a\equiv b$ (mod $m$) then $a^n\equiv b^n$ (mod $m$)
2. If $a\equiv b$ (mod $m$) and $c\equiv d$ (mod $m$) then $a+c\equiv b+d$ (mod $m$)

Now $2\equiv 2$ (mod $5$) and $3\equiv -2$ (mod $5$), so for any odd $k$, $3^k\equiv (-2)^k\equiv -2^k$ (mod $5$) using rule (1), and therefore $2^k+3^k\equiv 2^k-2^k\equiv 0$ (mod $5$) by rule (2). In other words, $5$ divides $2^k+3^k$ for any odd $k$.

Edward solved the remaining parts using modular arithmetic.

(c) $2^{99}\equiv 0$ (mod $2$), and $1^{99}+3^{99}\equiv 1+1\equiv 0$ (mod $2$) so $1^{99}+2^{99}+3^{99}$ is divisible by $2$.

(d) $2^{99}+3^{99}\equiv 0$ (mod $5$) by part (b). Similarly, since $4\equiv -1$ (mod $5$), $1^{99}+4^{99}\equiv 1^{99}+(-1)^{99}\equiv 0$ (mod $5$). Therefore $1^{99}+2^{99}+3^{99}+4^{99}$ is divisible by $5$.

We will leave parts (e)-(h) for the reader. See if you can use modular arithmetic to prove them.

We also received a nice solution from Yike, who concentrated on the last digits of the numbers and found various patterns. Can you prove that these patterns hold for all natural numbers? Why not try using modular arithmetic?