Compute $1008^{189642}\pmod{2011}$ How to begin computation of $1008^{189642}\pmod{2011}$
I am quite lost trying to figure out how to go about this. 
There are some "facts" I can find, but not sure how these can help me


*

*gcd(2011,1008) = 1. 

*2011 is prime.

*Prime factorisation of $1008$ is $2^4\times3^2\times7$

 A: A pedestrian solution:
By Fermat's little theorem, $1008^{2010}\equiv 1 \bmod 2011$, and since $189642\equiv 702 \bmod 2010$, we get $1008^{189642}\equiv 1008^{702} \bmod 2011$.
A few iterations yield $1008^9\equiv 48 \bmod 2011$, hence $1008^{702} \equiv 48^{78} \bmod 2011 $.
Noting that $48^3 \equiv -13 \bmod 2011$, we get $48^{78}\equiv 13^{26}  \bmod 2011$.
Finally, $13^{26}  = 13^{15}\cdot 13^{11}\equiv 74 \cdot 183 \equiv 1476 \bmod 2011$.
Putting everything together, $1008^{189642}\equiv 1476 \bmod 2011$.
A: Our starting point (see the other answers) is to calculate $1008^{702} \bmod 2011$.
Using the law of exponents and a base $2$ representation of $702$ (it translates into bracket placement), we need to calculate
$\quad x^{702} \equiv ((((((((x^2)^2)^2)^2)^2)^2)^2)^2)^2\; \times $
$\quad \quad \quad \quad \quad  ((((((x^2)^2)^2)^2)^2)^2)^2 \; \times$
$\quad \quad \quad \quad \quad ((((x^2)^2)^2)^2)^2\;  \times$
$\quad \quad \quad \quad \quad  (((x^2)^2)^2)^2 \; \times$
$\quad \quad \quad \quad \quad ((x^2)^2)^2\; \times$
$\quad \quad \quad \quad \quad (x^2)^2 \; \times$
$\quad \quad \quad \quad \quad x^2 \pmod {2011} \quad \text{where } x = 1008$
Setting constants and performing $\text{modulo } 2011$  calculations from the bottom up,
$\quad A = 1008^2 = 509$
$\quad B = 509^2 = 1673$
$\quad C = 1673^2 = 1628$
$\quad D = 1628^2 = 1897$
$\quad E = 1897^2 = 930$
$\quad F = 930^2 = 170\quad$ * intermediate
$\quad G = 170^2 = 746$
$\quad H = 746^2 = 1480\quad$ * intermediate
$\quad I = 1480^2 = 421$
ANS: $IGEDCBA \pmod {2011} \equiv 1476$
