Inverting Modular Exponentiation

Question

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?

Answer 1

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

Answer 2

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

Answer 3

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.

Answer 4

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