using Fermat's little theorem to reduce a large number mod a prime i want to show that $2^{70}\equiv 10 \pmod{13}$ using Fermat's little theorem. I see that 
$2^{12}\equiv 1 \pmod{13}$ hence $2^{60}\equiv 1 \pmod{13}$ so  $2^{70}\equiv 2^{10} \pmod{13}$ but i don't see how to finish this without evaluating $2^{10}$.
 A: What's so bad about evaluating $2^{10}$ modulo $13$? I can do it without help of pencil and paper: $2^4=16\equiv 3$ so $2^5\equiv2\times3=6$ and $2^{10}=(2^5)^2\equiv6^2=36\equiv10$ all modulo $13$. Or you could use $2^{72}\equiv1$ so $2^{70}\equiv2^{-2}=7^2$ since $7=\frac{13+1}2$ is the inverse of $2$ modulo $13$.
A: Hint $\ $ By little Fermat$\rm\ \ 2^{12}\equiv 1\ \Rightarrow\ 2^{72}\equiv 1\ \Rightarrow\ 2^{70}\equiv \dfrac{1}{2^2}\equiv\: \dfrac{-12}4 \equiv -3\pmod{13}$
More generally, one can easily invert any factor of modulus $\!\pm 1$
$$\rm  M = AB\mp 1\ \ \Rightarrow\ \ A^{\:\!-1\:+\:K\:\phi(M)}\:\equiv\: A^{-1}\:\equiv\: \pm B\ \ (mod\ M)$$
A: At some point in these things it is obvious that you are going to have to do some kind of calculaton, not every power is evenly divisible by $12$.
However it IS clear that in the end you will always get a power inbetween $0$ and $11$. These can be worked out easily by taking it one step at a time and reducing along the way...you will NOT have to work out the value of $2^{10}$ here but it is enough to work out say $2^5$, reduce mod $13$ and then square the answer.
