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

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.

• – Pp.. Feb 6 '15 at 18:04
• Hint: $2^{4} = 16$. – Alex Wertheim Feb 6 '15 at 18:05
• $2^{2999999} = 2^{4 \cdot 749999 + 3} = (-1)^{749999} \cdot 8 (mod 17) = -8 (mod 17) = 9(mod17)$ – Leafar Feb 6 '15 at 18:08

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$.

• In Mathjax, you might find it helpful to use \mod – Simon S Feb 6 '15 at 18:22
• @SimonS: \pmod{...} – barak manos Feb 6 '15 at 18:23
• In addition, it doesn't answer the case of $3^{123456789}\pmod{17}$, though I think that OP added it into the question at a later point. – barak manos Feb 6 '15 at 18:24
• @barakmanos \pmod is for equivalences. \mod is for the binary function $a\mod b$. Slightly different usages. Here \mod is correct. – Thomas Andrews Feb 6 '15 at 18:24
• @ThomasAndrews \bmod is actually the binary operator, straight \mod is (I think) a relation qualifier, so is spaced (much) further off. – Joffan Feb 7 '15 at 2:37

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.

• And what about $3^{123456789}\pmod{17}$? – barak manos Feb 6 '15 at 18:22
• @barakmanos Sorry, I'd read the question in the title - and how to do that by hand. To do the other note that $16|784 (=800-16)$ - only the last three digits matter, because the thousands digit is even - so that $x\equiv 3^5 = 243\equiv 73\equiv 5$. The question asks for a trick rather than a systematic approach. – Mark Bennet Feb 6 '15 at 18:31
• Yep, I read the "how to do it by hand" rather than "what's the trick"... – barak manos Feb 6 '15 at 18:32
• @barakmanos You are probably right - I read it quickly. – Mark Bennet Feb 6 '15 at 18:33
• Well, I guess that's the correct answer (at least more correct than my own, which does require a calculator)... – barak manos Feb 6 '15 at 18:34

$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$).

$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$.