Ask Uncle Colin: Powers and Remainders

Dear Uncle Colin,

I’m told that $2^a \equiv 9 \pmod{11}$. How do I find $a$?

– Powers And Stuff, Calculating And Learning

Hi, PASCAL, and thanks for your message!

As so often, there are (at least) two reasonable ways to tackle this: a brute force way and an elegant way.

Brutally

The numbers 2 and 11 are small enough that it’s not too difficult to calculate each of them, modulo 11.

  • $2^0 = 1 \equiv 1 \pmod{11}$
  • $2^1 = 2 \equiv 2 \pmod{11}$
  • $2^2 = 4 \equiv 4 \pmod{11}$
  • $2^3 = 8 \equiv 8 \pmod{11}$ (so far so obvious)
  • $2^4 = 16 \equiv 5 \pmod{11}$
  • $2^5 = 32 \equiv 10 \pmod{11}$
  • $2^6 = 64 \equiv 9 \pmod{11}$ … and we’re done.

At least, we’ve found a solution – in fact, there are infinitely many.

More elegantly

There’s a thing called Fermat’s Little Theorem, which is much less well known than his last one, but much more useful. It states that, if $p$ is a prime, then $b^{p-1} \equiv 1 \pmod{p}$ for all integers $b$.

For example, if $p=3$ and $b = 7$, Fermat says that $7^2 \equiv 1 \pmod{3}$, which is true: 49 is one more than a multiple of 3. For $p=5$ and $b = 3$, we’d expect $3^4 \equiv 1 \pmod{5}$, which is true again: 81 is one more than a multiple of 5.

The case we’re looking at here is somewhere Fermat applies: we have $b=2$ and $p=11$, which tells us that $2^{10} \equiv 1 \pmod{11}$ — if we were so minded, we could check that 1024 is indeed one more than a multiple of 111 .

Does this help? It does indeed. It turns out that all of the remainders you get from $b^k$, for $k=1$ to $k=p-1$, are unique. Since $\br{b^5}^2 = b^{10}$ and $b^5$ is not 1, it must be -1 — or 10, modulo 11.

Since 9 is the same as -2, modulo 11, $2^6$ must be 9, modulo 11.

However, we could multiply $2^6$ by $2^{10m}$, for any integer $m$, and get the same result, because $2^{10}$ is congruent to 1 (modulo 11).

That gives a final answer of $2^{6 + 10m}$ (for integer $m$).

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.

  1. It is $93 \times 11 + 1$. []

Share

Leave a Reply

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

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.

On twitter