Is there an easy way to calculate this modulo expression?

Question

$$3 ^ {3^{1000000000}} \bmod 1000000007$$

Also, is there a way to convert $a^{b^ c}$ to a form $d ^ e$ where $a \ne d$ and $e \ne b ^ c$?

Answer 1

By Fermat's little theorem, the problem boils down to computing $$ 3^{10^9}\pmod{500000003}. $$ That can be done by repeating $a\mapsto a^{10}\pmod{500000003}$ a few times. We have: $$\begin{eqnarray*} 3^{10}&\equiv& 59049\pmod{500000003} \\ 3^{10^2}&\equiv& 295914588\pmod{500000003} \\ 3^{10^3}&\equiv& 172803091\pmod{500000003} \\ &\ldots& \\ 3^{10^8}&\equiv& 299145277\pmod{500000003} \\ 3^{10^9}&\equiv& 283950619\pmod{500000003} \end{eqnarray*}$$ hence $3^{10^9}\equiv 283950619\pmod{1000000006}$ and $$ 3^{10^9}\equiv 3^{283950619} \equiv \color{red}{930782551}\pmod{1000000007} $$

This is clearly computer-assisted, since no one in his right mind would perform this amount (of simple, but lengthy) computations by hand.