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.
How to compute $7^{7^{7^{100}}} \bmod 100$?
3 Answers
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}$
-
2I gotta review my basic number theory,geez.......... – 2012-12-16
$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.