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

Leave a Reply

Your email address will not be published. Required fields are marked *

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.

On twitter