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 11 ((It is $93 \times 11 + 1$.)) .

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