modulus in number theory Find all solutions of x^11 ≡ 1 (mod 23). Justify your work
If I attempt to apply power of 11 to all values from 1-23, I get too large a value to then be able to see if it can be reduced modulo 23.
Is there a simpler way? any help would be appreciated
 A: When doing modular arithmetic you never need to deal with really big numbers because you reduce along the way. So for $2^{11} \pmod{23}$ you compute
$$
\begin{align}
2^2 & = 4\\
2^3 & = 8\\
2^4 & = 16\\
2^5 & = 32 \equiv 9\\
2^6 & \equiv 2 \times 9 = 18\\
2^7 & \equiv 2 \times 18 = 36 \equiv 13
\end{align}
$$
and so on.
There are other shortcuts that help with this particular problem, but the general principle (you never need big numbers) is worth remembering all the time.
A: By Euler's criterion, the solution is exactly the nonzero squares mod $23$.
So just compute $1^2, 2^2, \dots, 11^2 \bmod 23$.
A: Exponentiation by squaring is well-suited to such calculations (where needed) in modular arithmetic. As an example of how this can be used in this case:
\begin{align}
13^2 &= 169 \equiv 8 \bmod 23\\
13^4 &\equiv 8^2 \equiv 18 \bmod 23\\
13^8 &\equiv 18^2 \equiv (-5)^2 \equiv 25\equiv 2 \bmod 23\\
\text {and then}\qquad\\
13^{11} = 13^8\cdot13^2\cdot13^1 &\equiv 2\cdot8\cdot 13 \equiv 208 \equiv 1\bmod 23\\
\end{align}
In this case though, given that $a^{22}\equiv 1 \bmod 23$ for any $a$ coprime to $23$ by Fermat's little theorem, we just need to find all $b$ such that $b\equiv a^2\bmod 23$ for some $a$. In place of the above calculation, we find $6^2=36\equiv 13 \bmod 23$ and thus necessarily $13^{11}\equiv 6^{22}\equiv 1 \bmod 23$.
