Ask Uncle Colin: A modulus power

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 Colin

Colin is a Weymouth maths tutor, author of several Maths For Dummies books and A-level maths guides. He started Flying Colours Maths in 2008. He lives with an espresso pot and nothing to prove.

Share

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Sign up for the Sum Comfort newsletter and get a free e-book of mathematical quotations.

No spam ever, obviously.

Where do you teach?

I teach in my home in Abbotsbury Road, Weymouth.

It's a 15-minute walk from Weymouth station, and it's on bus routes 3, 8 and X53. On-road parking is available nearby.