Dear Uncle Colin,

How would you work out $9^{41} \pmod{61}$?

- Funky Exponential Result, Missed A Tutorial

Hi, FERMAT, and thanks for your question!

I think the answer is “ponderously”! There are only 61 possible answers (in fact, 60, because you know 61 is not a factor of $9^{41}$).

I’d start by playing around a bit: $9^2$ is 81, which is congruent to $20 \pmod{61}$.

Carrying on, $9^3 = 180 \equiv (-3) \pmod{61}$

That’s interesting - we now have a small number! Squaring it gives us $9^6 \equiv 9 \pmod{61}$, and we can check that $9^5 \equiv 1 \pmod{61}$ (in fact, it’s $968\times 61+1$.)

That’s great, because it tells us (in particular) that $\br{9^5}^8 = 9^{40} \equiv 1 \pmod{61}$, and that $9^{41} \equiv 9 \pmod{61}$.

Hope that helps!

- Uncle Colin