Better way to reduce $17^{136}\bmod 21$? What I have done:
Note $17\equiv -4$ mod 21, and $(-4)^2 \equiv 5$ mod 21. So $17^{136} \equiv (-4)^{136} \equiv 5^{68}$ mod 21. Also note $5^2 \equiv 4$ mod 21 and $4^3 \equiv 1$ mod 21, so $5^{68} \equiv 4^{34} \equiv (4^3)^{11}\cdot4 \equiv 4$ mod 21. I feel this is rather complicated, and there should be a better way. 
 A: One way that helps is to use Euler's Theorem, that, if $\gcd(a,n)=1$, then 
$$a^{\phi(n)} \equiv 1\bmod n.$$
So, since $\gcd(17,21)=1$ and $\phi(21)=12$, we have that
$$17^{136}\equiv 17^{136\bmod 12} \equiv 17^4 \bmod 21.$$
From here, one has $17^4 \equiv (-4)^4 = 256 \equiv 4\bmod 21$ - it reduces to a doable computation.
A: As $17\equiv-4\pmod{21},17^{2n}\equiv(-4)^{2n}$
$(-4)^{2n}=4^{2n}=(2^2)^{2n}=2^{4n}$
Now using Carmichael Function, $$\lambda(21)=\cdots=6$$
$$\implies2^{4n}\equiv2^{4n\pmod6}\pmod{21}$$
Here $2n=136\implies4n=272\equiv2\pmod6$
A: You could also reduce modulo each of the factors of $21$ and then use the Chinese Remainder Theorem to recover the result modulo $21$.
$$
  17^{136} \cong 2^{136} \cong (2^2)^{68} \cong 1^{68} \cong 1 \pmod{3}
$$
and
$$
  17^{136} \cong 3^{136} \cong 3^{6 \cdot 22 + 4} \cong (3^6)^{22} \cdot 3^4 \cong 1^{22} \cdot 3^4 \cong 3^4 \cong 9^2 \cong 2^2 \cong 4 \pmod{7} .
$$
Solving the system $x \cong 1 \pmod{3}$ and $x \cong 4 \pmod{7}$, we get $x \cong 4 \pmod{21}$. Therefore $17^{136} \cong 4 \pmod{21}$.
