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

Question

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).

Answer 1

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$.

Answer 2

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.

Answer 3

$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$.