<s>[INST] 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 ?
 [/INST] Since, by Fermat, $6^{22}\equiv1\pmod{23}$, we can try and see whether the order is $11$. Write $11=1+2+8$; then
$$
6^{11}\equiv 6\cdot 6^2\cdot ((6^2)^2)^2\pmod{23}
$$
Compute $6^2\equiv 13$, $13^2\equiv 8$ and $8^2\equiv18$, so
$$
6^{11}\equiv 6\cdot 13\cdot 18\equiv1
$$
Therefore, since $1000\equiv 10\pmod{11}$, we just observe that, since $6\cdot 4=24\equiv1\pmod{23}$, we have $6^{10}\equiv 4\pmod{23}$ (because the order is $11$, as shown before).
</s>