4
$\begingroup$

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.

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

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

$\endgroup$
  • $\begingroup$ In Mathjax, you might find it helpful to use \mod $\endgroup$ – Simon S Feb 6 '15 at 18:22
  • $\begingroup$ @SimonS: \pmod{...} $\endgroup$ – barak manos Feb 6 '15 at 18:23
  • $\begingroup$ 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. $\endgroup$ – barak manos Feb 6 '15 at 18:24
  • 2
    $\begingroup$ @barakmanos \pmod is for equivalences. \mod is for the binary function $a\mod b$. Slightly different usages. Here \mod is correct. $\endgroup$ – Thomas Andrews Feb 6 '15 at 18:24
  • $\begingroup$ @ThomasAndrews \bmod is actually the binary operator, straight \mod is (I think) a relation qualifier, so is spaced (much) further off. $\endgroup$ – Joffan Feb 7 '15 at 2:37
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ And what about $3^{123456789}\pmod{17}$? $\endgroup$ – barak manos Feb 6 '15 at 18:22
  • $\begingroup$ @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. $\endgroup$ – Mark Bennet Feb 6 '15 at 18:31
  • $\begingroup$ Yep, I read the "how to do it by hand" rather than "what's the trick"... $\endgroup$ – barak manos Feb 6 '15 at 18:32
  • $\begingroup$ @barakmanos You are probably right - I read it quickly. $\endgroup$ – Mark Bennet Feb 6 '15 at 18:33
  • $\begingroup$ Well, I guess that's the correct answer (at least more correct than my own, which does require a calculator)... $\endgroup$ – barak manos Feb 6 '15 at 18:34
0
$\begingroup$

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

$\endgroup$
-1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.