# Question 82f6f

Jun 3, 2016

The remainder of ${32}^{{32}^{32}}$ when divided by $7$ is $4$.

#### Explanation:

Putting the problem in terms of modular arithmetic, we are trying to reduce ${32}^{{32}^{32}}$ modulo $7$, that is

${32}^{{32}^{32}} \text{ (mod 7)}$

As $32$ and $7$ are coprime integers, we know by Euler's theorem that

${32}^{\varphi \left(7\right)} \equiv 1 \text{ (mod 7)}$

where $\varphi$ is Euler's totient function. Because $7$ is prime, we can easily calculate $\varphi \left(7\right)$ as $7 - 1 = 6$. With that, if we have ${32}^{32} = 6 q + r$ for positive integers $q$ and $r$, we can rewrite the problem as

${32}^{{32}^{32}} \equiv {32}^{6 q + r} \text{ (mod 7)}$

$\equiv {32}^{r} {32}^{6 q} \text{ (mod 7)}$

$\equiv {32}^{r} {\left({32}^{6}\right)}^{q} \text{ (mod 7)}$

$\equiv {32}^{r} {\left({32}^{\varphi \left(7\right)}\right)}^{q} \text{ (mod 7)}$

$\equiv {32}^{r} {\left(1\right)}^{q} \text{ (mod 7)}$

$\equiv {32}^{r} \text{ (mod 7)}$

To find $r$, then, we look at ${32}^{32} \text{ (mod 6)}$. Without needing any tricks, we can observe that for any integer $k > 0$, we have

$\left\{\begin{matrix}{2}^{2 k + 1} \equiv 2 \text{ (mod 6)" \\ 2^(2k)-=4" (mod 6)}\end{matrix}\right.$

$\implies {32}^{32} \equiv {\left({2}^{5}\right)}^{32} \equiv {2}^{5 \cdot 32} \equiv {2}^{2 \cdot 80} \equiv 4 \text{ (mod 6)}$

With the work above, that gives us

32^(32^32) -= 32^4" (mod 7)#

There are many ways to proceed from here, but noting that $2$ and $7$ are coprime, let's use the totient function again.

${32}^{4} \equiv {\left({2}^{5}\right)}^{4} \text{ (mod 7)}$

$\equiv {2}^{20} \text{ (mod 7)}$

$\equiv {2}^{2} \left({2}^{18}\right) \text{ (mod 7)}$

$\equiv 4 \left({2}^{6 \cdot 3}\right) \text{ (mod 7)}$

$\equiv 4 {\left({2}^{6}\right)}^{3} \text{ (mod 7)}$

$\equiv 4 {\left({2}^{\varphi \left(7\right)}\right)}^{3} \text{ (mod 7)}$

$\equiv 4 {\left(1\right)}^{3} \text{ (mod 7)}$

$\equiv 4 \text{ (mod 7)}$