How to solve $x \equiv 2^{2999999} \pmod {17}$?

Question

What trick can I use to solve the question (in the title)?

I need to solve it by hand, wihtout the help of a computer or calculator. And the trick shouldn't just work with my example but also with $3^{123456789}$ for example.

Answer 1

Write down the first few numbers. $2^0 \mod 17 = 1$. $2^1 \mod 17 = 2$. $2^2 \mod 17 = 4$. $2^3 \mod 17 = 8$. $2^4 \mod 17 = 16$. $2^5 \mod 17 = 15$. $2^6 \mod 17 = 13$. $2^7 \mod 17 = 9$. $2^8 \mod 17 = 1$.

Now if we go on with this, then the results will repeat. We will find that $2^8 = 2^{16} = 2^{24} ... \mod 17 = 1$. Every time the power is a multiple of eight, the modulo is 1. Therefore $2^{2999992} \mod 17 = 1$. And 7 steps further, $2^{2999999} \mod 17 = 9$.

Answer 2

Note that Fermat's little theorem tells us that $2^{16}\equiv 1 \bmod 17$

Now $2^{16n}=(2^{16})^n\equiv 1$

Next $2999999+1=3000000$ and $16\mid 3000000$ - if this is not obvious it is because $10000=16\cdot 625$ ($10^4=2^4\cdot 5^4$)

So that $2x\equiv 2^{3000000}\equiv 1\equiv 18$ and $x\equiv 9$

If Little Fermat is not available $2^4=16\equiv -1$ as in the comments gives $2^8\equiv 1$ and a similar argument works.

That can be done in your head and doesn't require dividing $2999999$ by anything.

Answer 3

$2^{16} \equiv 1\mod17$, and $2999999 = 187499 \times 16 + 15$, so we know $(2^{16})^{187499} \equiv 1\mod17$, so the answer is $2^{15}+1 \equiv 10\mod 17$.

Answer 4

$2^{16} \equiv 1$ (mod $17$), and $10000$ is divisible by $16$. Hence $2^{2999999} \equiv 2^{9999}$ (mod $17$). Since $2 \times 2^{9999} \equiv 1$ (mod $17$), so that $ 2^{9999} \equiv 9$ (mod $17$).

Similarly, $3^{123456789} \equiv 3^{6789} \equiv 3^{789}$ (mod $17$) since $6000$ is divisible by $16$. Now $789 = (16 \times 49) +5,$ so that $3^{789} \equiv 243 = (14 \times 17) +5 \equiv 5$ (mod $17$).