5
$\begingroup$

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

enter image description here

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

$\endgroup$
12
  • 1
    $\begingroup$ 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.$ $\endgroup$
    – md2perpe
    Sep 17, 2020 at 22:39
  • 4
    $\begingroup$ I don't think this deserves a downvote. There's clearly a lot of effort. $\endgroup$
    – Shaun
    Sep 17, 2020 at 22:51
  • 1
    $\begingroup$ If you insist on using brute force cycle determination then it would be better pedagogically to choose an example with period smaller than $100$. $\endgroup$ Sep 17, 2020 at 23:00
  • 1
    $\begingroup$ 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 $\endgroup$ Sep 18, 2020 at 0:20
  • 1
    $\begingroup$ Note that you know that the answer will be divisible by $8$ so you are only really interested modulo $125$ $\endgroup$ Sep 22, 2020 at 21:03

3 Answers 3

3
$\begingroup$

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

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

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.

$\endgroup$
3
  • $\begingroup$ May I ask why $N := (8^8 - 2) / 2$ is chosen? $\endgroup$ Sep 22, 2020 at 10:57
  • $\begingroup$ @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. $\endgroup$ Sep 22, 2020 at 21:01
  • $\begingroup$ Typo: "get a to a simple" should be "get to a..." $\endgroup$ Sep 22, 2020 at 21:15
0
$\begingroup$

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

$\endgroup$
12
  • 1
    $\begingroup$ @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. $\endgroup$
    – Arthur
    Sep 17, 2020 at 22:47
  • 3
    $\begingroup$ The question (including first version) explicitly asks for answers without using totient, so this is not an answer. $\endgroup$ Sep 17, 2020 at 22:54
  • 2
    $\begingroup$ OP said, " I would like to keep the explanation as basic as possible, without such devices as Euler's totient function, etc." $\endgroup$ Sep 17, 2020 at 23:00
  • 1
    $\begingroup$ @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. $\endgroup$ Sep 17, 2020 at 23:01
  • 1
    $\begingroup$ For the record: JCAA has deleted his comments that the prior three comments were in reply to. $\endgroup$ Sep 17, 2020 at 23:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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