Find all solutions to $y^2 \equiv 5x^3 \pmod {7}$

Question

Find all solutions to $y^2 \equiv 5x^3 \pmod {7}$

So basically one can evaluate all $a^2, 5b^3 \pmod {7}$ and look for all $(a,b) \in \mathbb Z_7\times \mathbb Z _7$ such that $a^2 \equiv 5b^3 \pmod 7$

Two questions:

1. Is that the "best" way doing it?
2. If I counted correctly there are exactly $7$ solutions. Is that a coincidence it equals to the modulus?

Thanks!

Answer 1

If $7\mid x\iff7|y$

else $7\nmid xy$

In that case as $\phi(7)=6, x^3\equiv\pm1\pmod7$

If $x^3\equiv1,y^2\equiv5$

Now as $y\equiv\pm1,\pm2,\pm3\pmod7, y^2\equiv1,4,9\equiv2$

Hence, $y^2\not\equiv5$

If $x^3\equiv-1,y^2\equiv-5\equiv2\equiv3^2\implies y\equiv\pm3$

Now $x^3\equiv1\implies x\equiv3,5\equiv-2,6\equiv-1\pmod7$

Answer 2

As $3$ is a primitive root $\pmod7$

and $3^2\equiv2\pmod7,3^3\equiv-1,3^5\equiv2\cdot-1\equiv5$

$$y^2\equiv5x^3\pmod7$$

$\iff2$ind$_3y\equiv5+3$ind$_3x\pmod6$ and $\phi(7)=6$

$\iff2($ind$_3y-1)\equiv3(1+$ind$_3x)\pmod6\ \ \ \ (1)$

Clearly, $3\mid($ind$_3y-1)$ and $2\mid(1+$ind$_3x)$

WLOG ind$_3y=1+3m$ where $m$ is any integer

$\implies$ind$_3x\equiv2m-1\pmod6$

$\implies y\equiv3^{1+3m},x\equiv3^{2m-1}\pmod7$

Answer 3

An approach which may save you some computation time (maybe 50%?) if you replace $7$ by a larger prime:

The left-hand side and the right-hand side vary independently in $x$ and $y$ so you are asking for which $x$ the number $5x^3$ is a square modulo 7. This can be computed via the Legende symbol.

The Legendre symbol is defined as $\newcommand\ls[2]{\left(\frac{#1}{#2}\right)}$

$$ \ls{a}{p} = \begin{cases} 1,& \text{ if $a$ is a square modulo $p$ and $a\not\equiv 0 \mod p$} \\ 0,& \text{ if $a\equiv 0$ modulo $p$} \\ -1,& \text{ otherwise.} \end{cases} $$

where $p$ is an odd prime number (e.g. $p=7$). There is an explicit formula:

$$ \ls{a}{p} = a^{\frac{p-1}{2}} \mod p $$

1. Using the multiplicativity, we get $$ \ls{5x^3}{7} = \ls{5}{7}\ls{x}{7}^3 $$
2. If $x = 0$, $y = 0$ (we don't need Legendre symbols for that)
3. If $x \neq 0$, then, because $7$ is prime, $\ls{x}{7}^2 = 1$, so $$ 1 \overset{!}= \ls{5x^3}{7} = \ls{5}{7}\ls{x}{7} $$

4. Therefore we need to find those $x$ with $$ -1 = \ls{5}{7} = \ls{x}{7} $$ with the help of the table on the Wikipedia page (or the explicit formula), we find $$ -1 = \ls{3}{7} = \ls{5}{7} = \ls{6}{7} $$

5. Thus $x \in \{0, 3,5,6 \}$. From that you can figure out the $y$: $$ (1^2,...,6^2) \equiv (1,4,2,2,4,1) \mod 7 $$ $$ (5\cdot 3^3, 5\cdot 5^3, 5\cdot 6^3) \equiv (2,2,2) \mod 7 $$ So $y \in \{ 3,4 \}$ in any case.

   All seven solutions: $\{ (0,0), (3,3), (3,4), (5,3), (5,4), (6,3), (6,4) \} $.

6. PS: Apparently there is a non-bruteforce way to compute $y$ (i.e. the square root of $5x^3$ modulo p), which works if $p = 4k+3$ for some natural number $k$ (which is the case for $p=7$).

   Then one root is $y_1 = (5x^3)^{k+1} \mod p$, and the other $y_2 = -y_1$.