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!

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