Find $6^{1000} \mod 23$ [duplicate]

$\begingroup$

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 ?

$\endgroup$ 1

4 Answers

$\begingroup$

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.

$\endgroup$ 2 $\begingroup$

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).

$\endgroup$ $\begingroup$

You can do the last steps by hand: for example $$6^2=36 \equiv 13 \mod 23$$ and $$6^4 \equiv13^2\equiv169\equiv8 \mod 23.$$ Now $$6^{10}\equiv 6^8\cdot6^2\equiv 8^2 \cdot 13 \equiv 18 \cdot 13\equiv 5 \cdot 10\equiv4 \mod 23$$

$\endgroup$ 1 $\begingroup$

$$3^3=27\equiv2^2\pmod{23}$$

$$\implies6^{1000}\equiv3\cdot2^{1000}(2^2)^{333}\equiv3\cdot2^{1666}$$

Method $\#1:$

As $2^5\equiv9,2^{11}=2\cdot9^2\equiv1\pmod{23}$ and $1666\equiv5\pmod{11}$

$2^{1666}\equiv2^5\pmod{23}\equiv9$

Method $\#2:$

Now $1666\equiv16\pmod{22}\implies2^{1666}\equiv2^{16}$

Now $2^8\equiv3\pmod{23}\implies2^{16}\equiv3^2$

$$\implies6^{1000}\equiv3\cdot3^2\equiv4$$

$\endgroup$