1
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ 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$ $\endgroup$ – Jakobian Sep 25 '18 at 12:50
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I think you wrote 360 instead of 320 in exponents' exponent. And how did you find $a (mod 400)$? $\endgroup$ – eagleye Sep 25 '18 at 13:52
  • $\begingroup$ @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 $\endgroup$ – Jakobian Sep 25 '18 at 13:56
  • 1
    $\begingroup$ Amazing, thanks a bunch! the second explanation really cleared things up. $\endgroup$ – eagleye Sep 25 '18 at 20:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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