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

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 ?

• Why don't you calculate by hand? Jan 15, 2016 at 9:09

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.

• I've just noticed that we have $1000 \equiv 10 \mod 22$ ,why can we use it to simplify $6^{1000}$ in $\mod 23$ ? Jan 15, 2016 at 9:39
• @Mr.Y: $$6^{1000} = 6^{10}\cdot(6^{22})^{45}.$$ Jan 15, 2016 at 9:40

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

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$$

• Thanks for your answer @mrprottolo.This is also pretty nice. Jan 15, 2016 at 9:15

$$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$$