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

Question

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?

Answer 1

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

Answer 2

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

Answer 3

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

Answer 4

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