# How to compute $7^{7^{7^{100}}} \bmod 100$?

How to compute $7^{7^{7^{100}}} \bmod 100$? Is $$7^{7^{7^{100}}} \equiv7^{7^{\left(7^{100} \bmod 100\right)}} \bmod 100?$$ Thank you very much.

-

First note that $$7^4 \equiv 1 \pmod{100}$$ Hence, we get that $$7^n \equiv \begin{cases}1 \pmod{100} & n \equiv 0 \pmod4\\ 7 \pmod{100} & n \equiv 1 \pmod4\\ 49 \pmod{100} & n \equiv 2 \pmod4\\ 43 \pmod{100} & n \equiv 3 \pmod4 \end{cases}$$ Hence, all we need to figure out is $7^{7^{100}} \pmod 4$. Since $7 \equiv (-1) \pmod4$, we have that $$7^{7^{100}} \equiv -1^{\text{odd}} \pmod 4 \equiv -1 \pmod 4 \equiv 3 \pmod 4$$ Hence, $$7^{7^{7^{100}}} \equiv 43 \pmod{100}$$

-
I gotta review my basic number theory,geez.......... –  Mathemagician1234 Dec 16 '12 at 9:32

$7^4\equiv1\pmod{100}$

Let $$y=7^{7^{7^{100}}}$$

So, $7y=7^{(7^{7^{100}}+1)}\equiv1\pmod{100}$ as $(7^{7^{100}}+1)$ is divisible by $(7+1)=8$

Let us use the property of the successive convergents of a continued fraction.

Now, $\frac{100}7=14+\frac27=14+\frac1{\frac72}=14+\frac1{3+\frac12}$

So, the previous convergent of $\frac{100}7$ is $14+\frac13=\frac{43}3$

So, $100\cdot3-7\cdot43=-1\implies y\equiv43\pmod {100}$

-

Since gcd(7, 100) = 1 you can use Euler's totient theorem.

$7^{\phi(100)} \equiv 7^{40} \equiv 1 \bmod 100$

where $\phi(n)$ is Euler's totient function.

Also note that $7^{\phi(40)} \equiv 7^{16}\equiv 1 \bmod 40$

so

$7^{7^{7^{100}}} \equiv 7^{(7^{7^{100}} \bmod 40)} \equiv 7^{(7^{(7^{100} \bmod 16} \bmod 40)} \bmod 100$

$7^{100} \equiv 1 \bmod 16$

$7^{7^{7^{100}}} \equiv 7^{(7^{(7^{100} \bmod 16} \bmod 40)} \equiv 7^{(7^{1} \bmod 40)} \equiv 7^{7} \equiv 43 \bmod 100$

Generally speaking, if you want to know $a^{b^{c^{d}}} \bmod m$, it is equal to $a^{b^{(c^{d \mod m_3} \mod m_2)} \mod m_1} \bmod m$

where $m_1 = \phi(m)$, $m_2 = \phi(m_1)$, $m_3 = \phi(m_2)$

provided that

$\gcd(a, m) = 1,$

$\gcd(b, m_1) = 1$ and

$\gcd(c, m_2)=1$.

If it is not, there is a trick that you can use $a^{b \mod \phi(m) + \phi(m)} \bmod m$ instead of $a^{b \mod \phi(m)} \bmod m.$

I was trying to get a discussion going at calculating nested exponents modulo n under exactly what circumstances this trick works, but my efforts were fruitless. If anyone knows anything about it, please consider visiting it and help.

-