5
$\begingroup$

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.

3 Answers 3

11

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

  • 2
    I gotta review my basic number theory,geez..........2012-12-16
2

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

1

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.