# Solution

Find $23^{534} \pmod{29}$ using fast exponentiation (i.e., successive squaring).

First we convert $534$ to binary:

$$\begin{array}{rcl} 534 &=& 2 \cdot 267 + 0\\ 267 &=& 2 \cdot 133 + 1\\ 133 &=& 2 \cdot 66 + 1\\ 66 &=& 2 \cdot 33 + 0\\ 33 &=& 2 \cdot 16 + 1\\ 16 &=& 2 \cdot 8 + 0\\ 8 &=& 2 \cdot 4 + 0\\ 4 &=& 2 \cdot 2 + 0\\ 2 &=& 2 \cdot 1 + 0\\ 1 &=& 2 \cdot 0 + 1\\ \end{array}$$

So $534 = 1000010110_2$.

Thus, $534 = 512 + 16 + 4 + 2$.

Now we compute some powers of $23\pmod{29}$ by successive squaring...

$$\begin{array}{rcccl} 23^{1} &\equiv& 23\\ 23^{2} &\equiv& 23^2 &\equiv& 529 &\equiv& 7\\ 23^{4} &\equiv& 7^2 &\equiv& 49 &\equiv& 20\\ 23^{8} &\equiv& 20^2 &\equiv& 400 &\equiv& 23\\ 23^{16} &\equiv& 23^2 &\equiv& 529 &\equiv& 7\\ 23^{32} &\equiv& 7^2 &\equiv& 49 &\equiv& 20\\ 23^{64} &\equiv& 20^2 &\equiv& 400 &\equiv& 23\\ 23^{128} &\equiv& 23^2 &\equiv& 529 &\equiv& 7\\ 23^{256} &\equiv& 7^2 &\equiv& 49 &\equiv& 20\\ 23^{512} &\equiv& 20^2 &\equiv& 400 &\equiv& 23\\ \end{array}$$

Note: not all of the calculation above is necessary, once when you get to $23^16 \equiv 7$ things have to repeat after that...

Multiplying the appropriate powers $\pmod{29}$, we have

$$\begin{array}{rcl} 23^{534} &=& 23^{512} \cdot 23^{16} \cdot 23^{4} \cdot 23^{2}\\ &\equiv& 23 \cdot 7 \cdot 20 \cdot 7\\ &=& 22540\\ &\equiv& 7 \end{array}$$