7
$\begingroup$

So far this is what I can do:

Using Fermat's Little Theorem I know that $3^{16}\equiv 1 \pmod {17} $

Also: $3^{2012} = (3^{16})^{125}*3^{12} \pmod{17}$

So I am left with $3^{12}\pmod{17}$.

Again I'm going to use fermat's theorem so: $ 3^{12} = \frac{3^{16}}{3^{4}} \pmod{17}$

Here I am stuck because I get $3^{-4} \pmod{17}$ and I don't know how to calculate this because I don't know what $\frac{1}{81} \pmod{17}$ is.

I know $81 = 13 \pmod{17}$

But I know the answer is 4. What did I do wrong?

$\endgroup$
  • 1
    $\begingroup$ Rather than calculate $\frac 1{81}$ why not calculate $81^3=3^{12}$? Note that $13^2\equiv(-4)^2\equiv -1\mod 17$... $\endgroup$ – abiessu Jan 23 '18 at 5:57
  • 1
    $\begingroup$ Hint: $\;3^4=81 = 5 \cdot 17 - 4\,$. $\endgroup$ – dxiv Jan 23 '18 at 5:58
  • 1
    $\begingroup$ You did nothing wrong. Notice that $81\times4\equiv1 \pmod{17}$. Either look at Bézout's identity and solve $81a+17b=1$ (using euclidean algorithm) and find why $a$ is your answer, or see the other comments for a direct computation. $\endgroup$ – Jean-Claude Arbaut Jan 23 '18 at 6:01
  • $\begingroup$ Interesting, so $81 = -4 \pmod{17}$, but what does that imply about $1/81 \pmod {17}$? $\endgroup$ – user81864 Jan 23 '18 at 6:01
  • $\begingroup$ @user81864 No need for $1/81$. You have $\,3^{12} \equiv (-4)^3=16 \cdot (-4) \equiv (-1)\cdot(-4) = 4\,$. $\endgroup$ – dxiv Jan 23 '18 at 6:02
1
$\begingroup$

$3^{12}=(3^3)^4=10^4$ (mod $17$), so we have to find $10000$ (mod $17$), which is evidently $4$ (mod $17$).

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

Indeed, we have $$3^{12}=31261\cdot17+4.$$

Also, $$3^{12}=81^3\equiv(-4)^3\equiv(-4)(-1)=4.$$

Also, we have $$3^{12}-4=(3^6-2)(3^6+2)=727\cdot731=727\cdot43\cdot17.$$

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

Just do it.

$3^4 = 81 \equiv -4$.

$3^{12} \equiv (3^4)^3 = (-4)^3 \equiv -81 \equiv 4 \mod 17$.

For insight:

You know $3^{16}\equiv 1 \mod 17$ so $3^{8}\equiv \pm 4$ so $3^4 \equiv \pm 1, \pm \sqrt{-1}$. So $-1 \equiv 16$ one of the $\sqrt {-1} \equiv 4\mod 17$. (the other is $13$). This should tell you to try to find $3^{12}$ via iterations $3^4$.

Also: $81 \equiv 13 \equiv - 4 \mod 17$. So $\frac 1{81} \equiv -\frac 14$. And figuring $\frac 14$ shouldn't be hard $1 \equiv 18$ so $\frac 12 \equiv 9 \mod 17$ and $9 \equiv 26$ so $\frac 14 \equiv 13\equiv -4$. So $-\frac 14 = 4$. And that makes sense. $(-4)*4 = -16 \equiv 1 \mod 17$.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

In addition to the clever answers, straightforward repeated squaring can be used. $$ 3^{12}=3^8 \cdot 3^4 $$ and $$ 3^2=9 \equiv 9 \mod 17 $$ so $$ 3^4 \equiv 9^2 \equiv 13 \mod 17 $$ and $$ 3^8 \equiv 13^2 \equiv 16 \mod 17 $$ so finally $$ 3^{12}=3^8 \cdot 3^4 \equiv 16 \cdot 13 \equiv 4 \mod 17 $$

The final line could be simplified further if desired $$ 16 \cdot 13 = 4 \cdot 52 \equiv 4 \cdot 1 \mod 17 $$

| cite | improve this answer | |
$\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.