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.
No comments:
Post a Comment