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?
 A: 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.$$
A: 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$.
A: $3^{12}=(3^3)^4=10^4$ (mod $17$), so we have to find $10000$ (mod $17$), which is evidently $4$ (mod $17$).
A: 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
$$
