Exponentiation of big numbers with Euler Theorem

Question

I need to compute $5^{12241} \pmod{13}$ and as suggestion I have that I should use the Euler's theorem.

The latter states that whether $a$ is relatively prime to $n$ then $a^{\phi(n)}=1\pmod{n}$.

But how this consideration can be used to compute the exponentiation of big numbers?

Answer 1

Since $\phi(13)=12$, the suggestion amounts to making use of the fact that $5^{12} = 1$ mod $13$. So for example $$5^{12241} = 5^{12000} \times 5^{240} \times 5^1 = (5^{12})^{1000} \times (5^{12})^{20} \times 5^1 = 1^{1000} \times 1^{20} \times 5 = 5 \,\,\text{mod $13$} $$

Answer 2

We don't need Fermat's Little Theorem or Totient theorem here

As $5^2\equiv-1\pmod{13},5^4\equiv1$

and $12241\equiv1\pmod4\implies5^{12241}\equiv5^1\pmod{13}$