Calculate modulo large number

Question

How do I calculate 4^23 mod 31? I think it can be done using Euler's Totient Function, but I don't know how.

Answer 1

This should be a relatively easy example. $4^{23}=2^{46}$. Now, since $2^5=32\equiv1\pmod{31}$,

$$2^{46}=(2^5)^9\times2=32^9\times2\equiv1\times2\equiv2\pmod{31}$$

Answer 2

It's easy enough to do by successive squaring:

\begin{align*} 4^1 &\equiv 4 \pmod{31} \\ 4^2 &\equiv 16 \pmod{31} \\ 4^4 &\equiv 16^2 \equiv 8 \pmod{31} \\ 4^8 &\equiv 8^2 \equiv 2 \pmod{31} \\ 4^{16} &\equiv 2^2 \equiv 4 \pmod{31} \end{align*}

Now use the fact that $23 = 16 + 4 + 2 + 1$.