1
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ It is true that $y \equiv 3 \pmod{7}$ is a solution. However, it is not the only solution. $\endgroup$ – N. F. Taussig Mar 5 '16 at 23:03
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.