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?
 A: The following is -in principle-still "searching" but structures the space to be searched into simpler subspaces:
$$ \begin{array}{} &4 &= y^4 \pmod 7 \\
& y^4 - 4 &\equiv 0 \pmod 7 \\
&(y^2 - 2)(y^2+2) &\equiv 0 \pmod 7 \\
&& \text{giving two factors}\\
&y^2 - 2 &\equiv 0 \pmod 7 \\
 \text{ or } & y^2 + 2 &\equiv 0 \pmod 7  \\
& y^2 &\equiv k \cdot 7 +2 & \to k=1,y^2=9 \text{ or } k=2,y^2=16 \text{ or ...}\\
 \text{ or }  & y^2 &\equiv j \cdot 7- 2  &\to k=?? \\
\end{array}$$
A: 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.
A: As far as I know, here is a way you can do this. Let a set $F$ be equal to: $$F = \{1, 16, 81, 256, 625, 1296, \cdot \cdot \cdot \}$$ which is every positive perfect fourth power. Now, let $d = y^4$ in which $d \in F$. Now, you are going to have to test each number (sorry, but guess and check is the only way I know for this one), and you'll get $d = 81$. So, for $d \ \text{mod} \ 7 = 4$, $d = 81$. But, you need to take the fourth root of that. When you calculate $\sqrt[4]{81}$, your answer is 3. So, your final answer is $y = 3$.
A: The only searching that needs to be done is to find where $4$ sits in $\Bbb F_7^\times$ with respect to a generator of this cyclic group of order six.
Now, $\Bbb F_7^\times$ has only the two generators $3$ and $5$, and $4$ is the square of $5$ modulo $7$. That is, calling $5=g$, we have $4\equiv g^2\pmod7$.
Equations in a cyclic group of order six can be reinterpreted as equations in the standard additive cyclic group $\Bbb Z/6\Bbb Z$. So, $4$, being the square of the generator, can be reinterpreted as twice the generator $1$ of $\Bbb Z/6\Bbb Z$. So our original equation $4\equiv y^4\pmod7$ to be solved for $y$ gets reinterpreted as $2\equiv4x\pmod6$. This is equivalent to $1\equiv2x\pmod3$, which you know has the single congruence-solution $x\equiv2\pmod3$. This is your solution: $y^4\equiv4\pmod7$ if and only if $y=g^x$ with $x\equiv2\pmod3$, in other words $x\equiv2,5\pmod6$, in other words $y\equiv5^2\text{ or }5^5\pmod7$, in other words $y\equiv4,3\pmod7$.
