Efficient way to solve $31^6 \mod 189$ without using any external devices. Assuming basic knowledge of modulus arithmetic, is there a way, a trick or formulas that allow you to solve modulus question with very large numbers without using calculator? For example, 

$$76^7 \mod 187=32$$ $$7^{23} \mod 143=2$$

This question ties into RSA Encryption where I'm trying to figure out how to solve these questions. So if I have $31^6 \mod 189$, I can simply use Wolfram Alpha but how can I work out that $31^6 \mod 189$?
Chinese remainder theorem int tandem with Eulers theorem will reduce is as far as possible.  As to whether the calculations are easy or not is another issue.

So $31^6 \mod 189$.  $189 = 7*3^3$ so by chinese remainder theorem we can solve this by solving $31^6 \mod 7$ and $31^6 \mod 27$.

So $7$ is prime and $31$ is not a multiple of $7$ we know $31^{7-1}\equiv 1 \mod 7$ so ... that's that.  And $\phi(27) = 3^2*2 = 18$ so $31^6 \equiv .... \mod 37$.  Well, it's a cube root of one but ... $31^6 \equiv 4^6 \equiv (3+1)^6 \equiv {6 \choose 2}3^2 + 6*3 + 1 \equiv \frac {6*5}2*3^2 + 18 + 1\equiv 19\mod 27$ ... or $4^6 \equiv 64^2 \equiv 10^2 \equiv 100 \equiv 19 \mod 27$.

So $31^6 \equiv 1 + 7k \equiv 19 + 27j \mod 189$.  By CRT there is one solution.

So solve $1 + 7k = 19 + 27j$

$27 = 4*7 - 1$

$1 = 4*7 - 27$.

$1 + 7k = 19 + 27j$

$7k - 27j = 18 = 21 - 3 = 3*7 - 3(4*7 - 27) = -9*7 +3*27$.

So if $k = -9$ and $j = -3$ we get $1-7*9 = -62$ and $19 - 3*27 =-62$ 

And so $31^6 \equiv -62 \equiv 127 \mod 189$
$31^2=961$ and $5\times 189=945$ so that $31^6\equiv 16^3$ and if you know your powers of $2$ this is efficiently sorted.