<s>[INST] How to efficiently compute $17^{23} (\mod 31)$ by hand? I could use that $17^{2} \equiv 10 (\mod 31)$ and express $17^{23}$ as $17^{16}.17^{4}.17^{3} = (((17^2)^2)^2)^2.(17^2)^2.17^2.17$ and take advantage of the fact that I can more easily work with powers of ten ($17^2 \equiv 10 (\mod 31), (17^2)^2 \equiv 100 (\mod 31) \equiv 7 (\mod 31)$, etc.). While this makes the computation easier, I'm thinking there might be a better way to do this.
 [/INST] Note that $17\equiv 3/2 \pmod {31}$.  We can then calculate this.
$2^5 = 1$, so $2^{23}=8$.
$3^3 = -4$, so $3^6 = 16$.  We then have $3^{24} = 16^4 = 2$, and dividing through by $8$, we get $8$.  Divide this by $3$ to get $31+8 = 39$, divide by 3 to get $13$.
</s>