Find all solutions to $y^2 \equiv 5x^3 \pmod {7}$ 
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: 


*

*Is that the "best" way doing it?

*If I counted correctly there are exactly $7$ solutions. Is that a coincidence it equals to the modulus? 


Thanks!
 A: 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 $$


*

*Using the multiplicativity, we get
$$ \ls{5x^3}{7} = \ls{5}{7}\ls{x}{7}^3 $$

*If $x = 0$, $y = 0$ (we don't need Legendre symbols for that)

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

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

*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) \} $.

*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$.
A: 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$
A: 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$
