elementary number theory - Find $6^{1000} mod 23$

Find $6^{1000} \mod 23$

Having just studied Fermat's theorem I've applied $6^{22}\equiv 1 \mod 23$, but now I am quite clueless on the best way to proceed.

This is what I've tried:

Raising everything to the $4th$ power I have

$$6^{88} \equiv 1 \mod 23$$ $$6^{100} \equiv 6^{12} \mod 23$$ $$6^{1000}\equiv 6^{120} \mod 23$$ $$6^{1000} \equiv 6^{10} \mod 23$$ How do I simplify now the right hand side of the congruence ?

Answer

We may exploit the fact that $1000\equiv 10\pmod{22}$ to get:

$$6^{1000}\equiv 6^{10} \equiv (6^5)^2 \equiv 2^2 \equiv\color{red}{4}\pmod{23}.$$
As an alternative, we may notice that $a^{11}\pmod{23}$ is the Legendre symbol $\left(\frac{a}{23}\right)$, so:

$$6^{11} \equiv \left(\frac{2}{23}\right)\cdot\left(\frac{3}{23}\right) \equiv 1\cdot 1\equiv 1\pmod{23}$$
gives $6^{1001}\equiv 1\pmod{23}$ and by multiplying both sides by the inverse of $6$ we get $4$ as above.