# Is there a quicker proof to show that $2^{10^k} \equiv 7 \pmod{9}$ for all positive integers $k$?

I noticed this pattern while playing with digit sums and noticed that the recursive digit sums (until you arrive at a single digit number) of numbers like, $2^{10}$, $2^{100}$, $2^{1000}$ and so on is always $7$. So, I decided to find out if it is true that for all positive integers $k$,

$$2^{10^k} \equiv 7 \pmod{9}$$

My proof is as follows:

Lemma 1. $\, 10^k \equiv 4 \pmod{6}$ for all integers $k \geq 1$

Proof. For all integers $k \geq 1$, the number $10^k + 2$ must be divisible by $6$ since it is even (implying divisibility by $2$), and its digit sum is $3$ (implying divisibility by $3$). Therefore, you can show that \begin{align*} 10^k + 2 &\equiv 0 \pmod{6} \\ 10^k &\equiv 4 \pmod{6} \,\, \text{ for all integers } k \geq 1 \end{align*}

Lemma 2. $\, 2^{4 + 6k} \equiv 7 \pmod{9}$, for all integers $k \geq 0$

Proof. If $a \equiv c \pmod{n}$ and $b \equiv d \pmod{n}$, then $a\,b \equiv c\,d \pmod{n}$. And, by extension, $a\,b^k \equiv c\,d^k \pmod{n}$ (for integers $k \geq 0$). Therefore, with \begin{align*} 2^4 \equiv 16 \equiv 7 \pmod{9} \end{align*} and \begin{align*} 2^6 \equiv 64 \equiv 1 \pmod{9} \end{align*} we can show that, \begin{align*} 2^{4 + 6k} \equiv 7 \cdot 1^k \equiv 7 \pmod{9} \,\, \text{ for all integers } k \geq 0 \end{align*}

Theorem. $\, 2^{10^k} \equiv 7 \pmod{9}$ for all integers $k \geq 1$

Lemma 1 implies that for all integers $k \geq 1$, $10^k = 4 + 6n$ where $n$ is some positive integer. Therefore, \begin{align*} 2^{10^k} &= 2^{4 + 6n} \\ 2^{10^k} \!\!\!\! \mod a &= 2^{4 + 6n} \!\!\!\! \mod a \end{align*} for any positive integer $a$. Using this result along with Lemma 2, \begin{align*} 2^{10^k} \equiv 7 \pmod{9} \,\, \text{ for all integers } k \geq 1 \end{align*} $$\tag*{\blacksquare}$$

I think the proof is correct, but I am not a fan of it. Mainly because, I think proving Lemma 2 is a much too long a way to prove this theorem - since it proves a generalization of the theorem first. Also, I discovered that lemma numerically, which feels a bit like cheating.

Either way, is there a quicker, more elegant proof which does not:

1. Use Lemma 2, or prove some generalization of the theorem first.

2. Uses Euler's Theorem. I feel that using Euler's Theorem is using a needlessly complicated theorem to prove something as simple as this.

I am sure some of the people here can come up with single line proofs. I am curious to see if there's such a proof.

• euler's theorem is one of the basic tools when working with exponents – HereToRelax Sep 3 '16 at 1:13
• Do you mean is there a shorter proof ? – Rene Schipperus Sep 3 '16 at 1:14
• Well...$2^{10}\equiv 7\pmod 9$ and $7^{10}\equiv 7\pmod 9$. Then go by induction. – lulu Sep 3 '16 at 1:14
• "I feel using Euler's theorem is using a needlessly complicated theorem to prove something as simple as this" well, that is just silly! The entire reason to have complicated theorems is because they are versitile and so you won't have to prove simple propositions like this over and over again. "Proof: it follows directly from Euler's theorem". That is a six word proof and it is enough! It's ... silly... to give a six paragraph 2 lemma prove and then complain a six word proof is too complicated. It's not like we have prove Euler th. Every time we use it. – fleablood Sep 3 '16 at 4:46
• @fleablood Moise once referred to it as something like using a tractor where a shovel would do. It's very natural to wonder if there is a more elementary solution. There is nothing inherently wrong with finding more than one way to solve a problem. How many proofs of quadratic reciprocity exists? – steven gregory Jan 2 '18 at 15:41

## 2 Answers

Induction? Base case when $k=1$ is clear, for inductive step we have: $2^{10^k}=(2^{10^{k-1}})^{10}\equiv 7^{10}\equiv 7\bmod 9$

• How did you get $7^{10} \equiv 7 \pmod{9}$ without evaluating in a computer? – XYZT Sep 3 '16 at 1:40
• we can go $7^{10}\equiv (-2)^{10}\equiv 2^{10}$. And you already know $2^{10}\equiv 9$. So we don't need no extra stuff – HereToRelax Sep 3 '16 at 1:43
• @CarryonSmiling You mean $2^{10}\equiv 7$. It simply follows from $1+0+2+4\equiv 7\pmod{9}$. – user236182 Sep 3 '16 at 5:09

Don't fear Euler's theorem. You have it. Use it. It's not like it costs a lot of gas money or you have to pay tolls.

$2^6 \equiv 1 \mod 9$ so $2^{10^k} \equiv 2^{(10^k \mod 6 = 4^k \mod 6)} \mod 9$.

One little observation. If $4^n \equiv 4 \mod 6$ then $4^{n+1} \equiv 16 \equiv 4 \mod 6$ so inductively $4^n \equiv 4 \mod 6$ for all $n$.

So $2^{10^k} \equiv 2^{4^k} \equiv 2^4 =16 \equiv 7 \mod 9$.