<s>[INST] Inverting Modular Exponentiation How can I go about solving the equation $4 = y^4 \bmod{7}$?  Do I have to try all of the possible $y$'s in between $1$ and $7-2$ or is there a smarter way that can be generalized for larger numbers?
 [/INST] First, factor the equivalence as a difference of squares.
\begin{align*}
y^4 & \equiv 4 \pmod{7}\\
y^4 - 4 & \equiv 0 \pmod{7}\\
(y^2 + 2)(y^2 - 2) & \equiv 0 \pmod{7}
\end{align*}
Hence, $$y^2 + 2 \equiv 0 \pmod{7} \implies y^2 \equiv -2 \equiv 5 \pmod{7}$$ or $$y^2 - 2 \equiv 0 \pmod{7} \implies y^2 \equiv 2 \pmod{7}$$
Observe that
\begin{align*}
4 & \equiv -3 \pmod{7}\\
5 & \equiv -2 \pmod{7}\\
6 & \equiv -1 \pmod{7}
\end{align*}
and that
\begin{align*}
0^2 & \equiv 0 \pmod{7}\\
1^2 & \equiv (-1)^2 \equiv 1 \pmod{7}\\
2^2 & \equiv (-2)^2 \equiv 4 \pmod{7}\\
3^2 & \equiv (-3)^2 \equiv 9 \equiv 2 \pmod{7}
\end{align*}
Hence, $y \equiv 3 \pmod{7}$ or $y \equiv -3 \equiv 4 \pmod{7}$, which you can check by direct substitution.
</s>