# Find 3 last digits of power of power where base is huge

Given $$a=135797531$$, find 3 last digits of $$a^{a^{320}}$$.

Now, I know that I need to solve: $$a^{a^{320}}(\mod 1000)$$.

What I know: $$a\in{U_n}$$ (Euler's group - Multiplicative group of integers modulo n) so that means Euler's theorem applies and $$a^{\phi(1000)}\equiv1(\mod 1000)$$ where $$\phi(1000)=400$$.

I also saw here that the exponent is congruent to the exponent modulo $$\phi(1000)$$ but I don't understand why and under what conditions..

I don't know how to continue from here..help!

• Calculate $b=a\,\text{mod}\,1000$ and $c=a\,\text{mod}\,400$ then you'll need to find $b^{c^{320}}$. We can then calculate $\varphi(400)$ and use Euler's theorem again to reduce the power of $320$ – Jakobian Sep 25 '18 at 12:50

Theorem: If $$b$$ and $$c$$ are non-negative natural numbers, $$m$$ and $$a$$ are co-prime, $$b = c\enspace\text{mod}\,\varphi(m)$$, then $$a^b = a^c\enspace\text{mod}\,m$$.

Proof: Without loss of generality, suppose that $$b>c$$. Then $$b=c+k\cdot\varphi(m)$$ where $$k$$ is a natural number. $$a^b = a^{c+k\cdot\varphi(m)} = a^c\cdot (a^{\varphi(m)})^k = a^c \enspace\text{mod}\,m$$

Where we used Euler's theorem for $$a^{\varphi(m)} = 1\enspace\text{mod}\,m$$, and the fact that $$a'=a''\enspace\text{mod}\,m\,\land\,b'=b''\enspace\text{mod}\,m\implies a'b'=a''b''\enspace\text{mod}\,m$$

End of proof.

Suppose we want to calculate $$a^{a^{320}}$$ modulo $$1000$$. We can first calculate $$a^{320}$$ modulo $$\varphi(1000)=400$$ since $$a$$ and $$1000$$ are co-prime, using the theorem above.

To calculate $$a^{320}$$ modulo $$400$$, we can calculate $$320$$ modulo $$\varphi(400)=160$$, because, again, $$400$$ and $$a$$ are co-prime.

$$320 = 0\enspace\text{mod}\,160 \implies a^{320} = 1\enspace\text{mod}\,400 \implies a^{a^{320}}=a\enspace\text{mod}\,1000$$ And because $$a=531\enspace\text{mod}\,1000$$, then $$a^{a^{320}}=531\enspace\text{mod}\,1000$$

• I think you wrote 360 instead of 320 in exponents' exponent. And how did you find $a (mod 400)$? – eagleye Sep 25 '18 at 13:52
• @eagleye yes, you're right, thanks. I've edited my post for more clarity, and also corrected my mistakes. It's a lot easier now that there's $320$ in exponent – Jakobian Sep 25 '18 at 13:56
• Amazing, thanks a bunch! the second explanation really cleared things up. – eagleye Sep 25 '18 at 20:57