Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

3 Answers

up vote 11 down vote accepted

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

share|improve this answer
2  
I gotta review my basic number theory,geez.......... –  Mathemagician1234 Dec 16 '12 at 9:32
add comment

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

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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