The most efficient way to solve $2^{2017} \mod 9$

Question

I have just started my Computational Algebra course and I have to solve this relatively easy problem: $$2^{2017} \mod 9$$ The first thing that I noticed was that $2$ and $9$ are coprime, therefore, I can use the Euler theorem to conclude that: (Congruence in terms of $\mod 9$ $$2^{\varphi(9)} \equiv 1$$ I calculate $\varphi(9)$ manually and get $6$, therefore $$2^6 \equiv1$$ Notice that $2^{2017} = (2^6)^{336} \cdot 2$ and so $$2^{2017} \mod 9 = (2^6)^{336} \cdot 2 \mod 9 = \\ = (2 \mod 9)(\mod9) = 2$$

However, I am pretty sure that there exists an easier way to solve this without resorting to such sophisticated theorems. Have you got any ideas?

Answer 1

Since $2^3\equiv-1\pmod9$, $2^6\equiv1\pmod9$. But $2\,017\equiv1\pmod6$. Therefore, $2^{2\,017}\equiv2\pmod9$.

Answer 2

$2^3=8\equiv-1$ mod $9$ and $2017=1+3\cdot672$, so

$$2^{2017}=2\cdot(2^3)^{672}\equiv2(-1)^{672}=2\mod 9$$

Answer 3

By successive doublings modulo $9$, $$2^6\bmod9= 1.$$

Then $$2^{2017}\bmod9=2^{2017\bmod 6}=2^1.$$

Answer 4

You use the words "sophisticated" and "efficient".

I believe those to be contradictory.

$2^{2017}\equiv 2^{2017 \mod \phi(9)= 6} \equiv 2^{2017\equiv 1 \mod 6} \equiv 2^1 = 2 \mod 9$.

is VERY efficient and is the most efficient way you can do this.

But you complain it is too "sophisticated". Why is that a problem? Okay, it violates the "explain it to my like I was 5" concept.

Okay, there are less sophisticated ways. But they are less efficient.

And the easiest way is brute force:

$1,2,2^2,2^3,.... etc.$ will eventually have to repeat. So we have to find out when it repeats. It we do that by punching. As there are only $9$ possible values the $2^k$ can be equivalent to, we can rest in knowing we'll only have to punch at most nine times.

$1 ,2, 2^2, 2^3 ,.... \equiv 1,2,4,8,16 \equiv 7, 32\equiv 5, 64 \equiv 1$. That's it. It repeats every $6$ times.

(We could have more efficiently noticed we don't need to do $2*16=32\equiv 5$ but $2*7=14 \equiv 5$ and $2*5=1 \equiv 1$ rather than $2*32 = 64 \equiv 1$. But that would have required sophistication.)

So $2^{2017 = 1 + 6*k} \equiv 2^1 \equiv 1 \mod 9$.

That was very easy. But not very efficient.

Perhaps the best compromise is to note that $2^3 =8\equiv -1 \mod 9$ so $2^6\equiv 1 \mod 9$ and take it from there.

But that requires insight and insight is not something that can be taught.

So your three options:

"sophistication": You have a theorem that tells you how to do this explicitely and directly. Can't get any more efficient than that.

"simplicity": You can just do it by brute force. Can't get any easier or less efficient than that.

"insight": Works if you've got it. (Sucks if you don't.)

Which of those three work the best will be a matter of taste, experience, and style.

==== old answer ===

Depends on what you call "efficient".

$\gcd(2,9)=1$ and $\phi(9) = 6$ so $2^6\equiv 1 \mod 9$ by Eulers theorem so $2^{2017} \equiv 2^{2017\mod 6}\equiv 2^1 \equiv 2 \mod 9$.

But is that efficient? It is if you are comfortable with Euler's theorem.

Or $2^3 = 8\equiv -1 \mod 9$ so $2^{2017} = 2^{2016}*2 \equiv (2^3)^{someevennumber}*2 \equiv (-1)^{someevennumber}*2 \equiv 1*2 \equiv 2 \mod 9$. Which is straightfoward brute force.

Or $2^3 = 8 \equiv 1$ so $2^6 \equiv (-1)^2 \equiv 1 \mod 9$. So $2^{2017} = 2^{2016}*2 = (2^6)^{somenumber}*2 \equiv 2 \mod 9$.

And if you didn't notice that $2^3 \equiv -1$?.... Then list out $2^0, 2^1, 2^2, ... \mod 9$ and see if there is a pattern.

$1,2,4, 8, 16\equiv 7, 14\equiv 5, 10\equiv 1, ... $ and from there it repeats. So $2^6 \equiv 1$ and $2^{a+6} \equiv 2^a$. So $2^{2017= 6*k + 1} \equiv 2^1 \equiv 1 \mod 9$.

Answer 5

$$2^{2017}=(3-1)^{2017}$$

Everything is divisible by $9$, when expanding, except the last two terms, which add up to $3\cdot 2017-1=672\cdot 9+2$. So: $$2^{2017}\equiv_9 2$$