# Find last three digits of $8^{8^8}$

I am attempting to find $$8^{8^8}$$ (which, by the way, means $$8^{(8^8)}$$) without any means such as computers/spreadsheets. Here's my attempt so far, and I'm pretty sure my answer is correct, but I would like a more efficient method.

First, I do the exponent: $$8^8=(2^3)^8=2^{24}$$, and I calculated that the last three digits are 216 by hand. I then know that $$8^{(8^8)}\equiv8^{216} \pmod{1000}$$, and so I have to calculate this and found that it repeats in cycles of $$100$$.

Using this information, I deduce that $$8^{(8^8)}\equiv8^{216}\equiv8^{200}\cdot8^{16}\equiv8^{16}\equiv2^{48}\equiv656\pmod{1000}$$

Is there is a more efficient way to solve this problem than just listing out all the remainders, as I have done? I would like to keep the explanation as basic as possible, without such devices as Euler's totient function, etc.

Someone has asked me if How do I compute $a^b\,\bmod c$ by hand? is what I wanted, but no, because I want to keep it as elementary as possible, and I also don't want any tedious calculations (as I have done).

• Using modulo of exponents is not valid. For example, $7 \equiv 2 \pmod 5$, but $2^7 = 128 \equiv 3 \pmod 5$ while $2^2 = 4 \equiv 4 \pmod 5.$ Sep 17, 2020 at 22:39
• I don't think this deserves a downvote. There's clearly a lot of effort. Sep 17, 2020 at 22:51
• If you insist on using brute force cycle determination then it would be better pedagogically to choose an example with period smaller than $100$. Sep 17, 2020 at 23:00
• It can be done easily by the first few terms of the Binomial Theorem without requiring any periodicity knowledge. If that is of interest let me know and I will post the details Sep 18, 2020 at 0:20
• Note that you know that the answer will be divisible by $8$ so you are only really interested modulo $125$ Sep 22, 2020 at 21:03

Without Euler's totient function, by repeated squaring, from $$8^8\equiv216\bmod1000$$,

we have $$8^{16}\equiv656\bmod1000$$, $$8^{32}\equiv336\bmod1000$$, $$8^{64}\equiv896\bmod1000$$,

and $$8^{128}\equiv816\bmod 1000$$, so $$8^{216}\equiv8^{128}8^{64}8^{16}8^8\equiv656\bmod1000.$$

And I would like to re-iterate the comment that $$c^a\equiv c^b\bmod n$$

does not generally follow from $$a\equiv b\bmod n$$.

• That's a lot of painful mod $1000$ multiplications that are left for the reader! Sep 18, 2020 at 0:49

Here is a way using only simple mod arithmetic and $$\,\rm\color{#90f}{BT}=$$ Binomial Theorem

Let $$\ N := (8^{\large 8}\!-\!2)/2 \equiv -18\,\pmod{\!125}.\,$$ Then by $$\,\rm\color{#90f}{BT}\,$$ & $$\, 65^{\large 3+k}\!\equiv 0\,$$ by $$\,5^{\large 3}\!\mid 65^{\large 3}\,$$ so

\qquad\ \ \ \begin{align} &8^{\large 8^8-2}\! = 8^{2N}\!\!= (-1\!+\!65)^N\!\equiv -1\! +\! N\cdot 65 - \tfrac{N(N-1)}2 65^2\equiv \color{#c00}{-21}\!\!\!\pmod{\!125}\\[.2em] \Rightarrow\ &8^{\large 8^8-1}\! \equiv 8(\color{#c00}{-21})\equiv \color{#0a0}{82}\!\pmod{\!125}\\[.2em] \Rightarrow\ &8^{\large 8^8}\!\!\equiv 8(\color{#0a0}{82})\equiv \bbox[5px,border:1px solid #c00]{656}\!\!\!\pmod{\!8\cdot 125} \end{align}

Stronger $$\,8^{\large 8^8}\!\!\equiv 6656\pmod{\!8000}\,$$ if we use $$\!\bmod 1000$$ in 2nd last congruence.

Generally the most efficient way to handle problems like this is to employ the extremely handy mDL = $$\!\bmod\!\!$$ Distributive Law as here to greatly decrease the modulus. Applying this law here we can pull out a factor of $$\,\color{#e0f}{a = 8}\,$$ from the modulus as follows
\begin{align} ab\,\bmod\, ac \,&=\, \color{#e0f}a(b\, \bmod\, c)^{\phantom{|^|}}\!\!\!\ \ \ \ [\!\bmod\text{Distributive Law}]\\[.1em] \Longrightarrow\ 8^{\large 2+2N}\! \bmod 1000 \,&=\, \color{#e0f}8(8^{\large 1+2N}\! \qquad\,\ \bmod 125)\\ &=\, 8(8(-1\!+\!65)^N\! \bmod 125)\\ &=\, 8(8(\color{#a00}{-21})\qquad\bmod{125})\ \ \ {\rm by} \ \ {\rm \color{#90f}{BT}\ as\ above,\ and}\,\ N\equiv -18\\ &=\, 8(\color{#0a0}{82})= 656_{\phantom{|_{|_|}}} \end{align}
Explanation: first we used mDL to factor out $$\,\color{#e0f}{a=8}\,$$ from the $$\!\bmod\!$$ to simplify the problem by reducing the modulus from $$\,8\cdot 125\,$$ to $$\,125.\,$$ So we have reduced to powering $$8$$ modulo $$125$$. By luck $$\,8^{\large 2}\equiv -1\!+\!65\equiv -1\pmod{\!5}$$ which we can lift up to $$\!\bmod 5^{\large 3}$$ by the Binomial Theorem, after writing $$\,8^{\large 1+2N}\! = 8(8^2)^N\! = 8(-1\!+\!65)^N,\,$$ leaving only simple mod arithmetic to finish.

• May I ask why $N := (8^8 - 2) / 2$ is chosen?
– Y.T.
Sep 22, 2020 at 10:57
• @LearningMathematics I added an explanation, using mDL to clarify the operations (this is the best way in general - compare the two approaches). Note $\,K = \color{#c00}2+\color{#0a0}2N\iff N = (K-2)/2.\,$ In OP $\,K = 8^8\,$ is our exponent. The red $\,\color{#c00}2\,$ corresponds to the two factors of $8$ we pull out, and the green $\,\color{#0a0}2\,$ comes from needing to square $\,8\,$ to get a to a simple form enabling us to easily lift powering from $\!\bmod 5\,$ up to $\bmod 5^3\,$ by the Binomial Theorem. Sep 22, 2020 at 21:01
• Typo: "get a to a simple" should be "get to a..." Sep 22, 2020 at 21:15

$$1000=8\cdot 125$$, so $$\phi(1000)=4\cdot4\cdot25=400$$, $$8^8\mod 400 = 16$$. Then $$8^{16}\mod 1000=656$$. So the answer is $$656$$.

• @KingLogic For the last digit, and possibly for the last two digits, you can likely just look at $8^n$, see a repeating pattern, use that pattern. For the last three digits, though, that approach feels like it's too much work to be worthwhile. I don't think there are other, easier approaches either. Sep 17, 2020 at 22:47
• The question (including first version) explicitly asks for answers without using totient, so this is not an answer. Sep 17, 2020 at 22:54
• OP said, " I would like to keep the explanation as basic as possible, without such devices as Euler's totient function, etc." Sep 17, 2020 at 23:00
• @JCAA You need to read more carefully - see the final paragraph of the question. Also your aswer still leaves a lot of work (exponentiation) to be performed, much of which would likely be nontrivial to beginners. Sep 17, 2020 at 23:01
• For the record: JCAA has deleted his comments that the prior three comments were in reply to. Sep 17, 2020 at 23:42

In a comment the OP stated

I would like an extremely elementary method, to teach to high school students with very little background in number theory.

To begin observe that

$$8^{8^8} = 8^{2^{24}}$$

So starting with $$8$$ we need to apply the squaring operation $$24$$ times. Moreover, at each step we only need to keep track of the last $$3$$ digits since the other digits in the base-$$10$$ expansion can't have an impact on them when squaring the numbers.

To save work we decide to find a more general squaring rule that can hopefully be reused. We'll use the formula

$$(s+t)^2 = s^2 + 2st + t^2$$

on the base-$$10$$ expansions to get our rules.

The $$\equiv$$ symbol will mean that two numbers have the same last $$3$$ digits.

To square $$8$$ and get the last $$3$$ digits observe, where $$0 \le a \le 9$$, that

$$\; \text{Rule08:} (a10^2 +08)^2 \equiv \quad 600a +64$$

So

$$\tag 1 8^2 \equiv 64$$

Continuing

$$\; \text{Rule64:} (a10^2 +64)^2 \equiv \quad 800a +96$$
$$\tag 2 {64}^2 \equiv 96$$
$$\; \text{Rule96:} (a10^2 +96)^2 \equiv \quad 200(a+1) + 16$$
$$\tag 3 {96}^2 \equiv 216$$
$$\; \text{Rule16:} (a10^2 +16)^2 \equiv \quad 200(a+1) + 56$$
$$\tag 4 {216}^2 \equiv 656$$
$$\; \text{Rule56:} (a10^2 +56)^2 \equiv \quad 200a+100 + 36$$
$$\tag 5 {656}^2 \equiv 336$$
$$\; \text{Rule36:} (a10^2 +36)^2 \equiv \quad 200(a+1) + 96$$
$$\tag 6 {336}^2 \equiv 896$$

We are happy to see that we can repeatedly apply the four rules

$$\text{Rule96} \mapsto \text{Rule16} \mapsto \text{Rule56} \mapsto \text{Rule36} \mapsto \dots$$

in a cycle; the following is all mental work.

$$\tag 7 {896}^2 \equiv 816$$
$$\tag 8 {816}^2 \equiv 856$$
$$\tag 9 {856}^2 \equiv 736$$
$$\tag {10} {736}^2 \equiv 696$$
$$\tag {11} {696}^2 \equiv 416$$
$$\tag {12} {416}^2 \equiv 056$$
$$\tag {13} {056}^2 \equiv 136$$
$$\tag {14} {136}^2 \equiv 496$$
$$\tag {15} {496}^2 \equiv 016$$
$$\tag {16} {016}^2 \equiv 256$$
$$\tag {17} {256}^2 \equiv 536$$
$$\tag {18} {536}^2 \equiv 296$$
$$\tag {19} {296}^2 \equiv 616$$
$$\tag {20} {616}^2 \equiv 456$$
$$\tag {21} {456}^2 \equiv 936$$
$$\tag {22} {936}^2 \equiv 096$$
$$\tag {23} {096}^2 \equiv 216$$
$$\tag {24} {216}^2 \equiv 656$$

Observe that $$8^{2^{22}} \equiv 8^{2^2} \equiv 096$$ so the squaring sequence was just starting to repeat - the last two rule based calculations were not necessary.