# How can I calculate the remainder of $3^{2012}$ modulo 17?

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?

• Rather than calculate $\frac 1{81}$ why not calculate $81^3=3^{12}$? Note that $13^2\equiv(-4)^2\equiv -1\mod 17$... – abiessu Jan 23 '18 at 5:57
• Hint: $\;3^4=81 = 5 \cdot 17 - 4\,$. – dxiv Jan 23 '18 at 5:58
• 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. – Jean-Claude Arbaut Jan 23 '18 at 6:01
• Interesting, so $81 = -4 \pmod{17}$, but what does that imply about $1/81 \pmod {17}$? – user81864 Jan 23 '18 at 6:01
• @user81864 No need for $1/81$. You have $\,3^{12} \equiv (-4)^3=16 \cdot (-4) \equiv (-1)\cdot(-4) = 4\,$. – dxiv Jan 23 '18 at 6:02

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

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

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

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