how to solve $\operatorname{rem}(6^{15},17)$ without using a calculator. I am trying to solve $\operatorname{rem}(6^{15}, 17)$.
I know that we have to use congruences but don't know how to go on.
$6 ≅ 6 \mod 17$??
Can anyone please point me in the right direction?
Do I have to use CRT in here?

A low tech solution:
$6^2 = 36 \equiv 2 \pmod{17}$ ($34$ is a multiple of $17$).
So $6^4 = (6^2)^2 \equiv 2^2 = 4 \pmod{17}$
Hence: $6^8 = (6^4)^2 \equiv 4^2 = 16 \equiv -1 \pmod{17}$ 
Also: $6^{15}=6^1 \cdot 6^2 \cdot 6^4 \cdot 6^8$ ($15$ is $1111$ in binary), so modulo $17$ this becomes
$6 \times 2 \times 4 \times -1 = -48 \equiv -48 + 3\times 17 = 3$
So $3$ is the answer. 
