Determine the number of solutions for quadratic equation modulo prime

Question

Given that $106$ is quadratic residue $\bmod\ 139$, how can I determine the number of solutions to the following equation?

$$x^2 \equiv 106 \pmod{139}$$

Answer 1

If $p$ is prime then $x^2\equiv a\pmod p$ has no solution, or exactly one, or exactly two. If $a$ is a quadratic residue modulo $p$, that rules out having no solution --- right? If $x$ is a solution, so is $-x$, right?

Answer 2

Since $106\equiv x_0^2 \ \ (139)$ we have $$139 | (x-x_0)(x+x_0)$$ By Euclid's lemma $x \equiv x_0 \ (139)$ or $x \equiv -x_0 \ (139)$. Therefore, you have two solutions.

Answer 3

$\,139\,$ is a prime and $\,139=3\pmod 4\,\,\,,\,\,139\neq \pm 1\pmod 8\,$ , so using the Legendre Symbol and the Law of Quadratic Reciprocity:

$$\left(\frac{106}{139}\right)=\left(\frac{53}{139}\right)\left(\frac{2}{139}\right)=-\left(\frac{139}{53}\right)=-\left(\frac{33}{53}\right)=-\left(\frac{3}{53}\right)\left(\frac{11}{53}\right)=$$

$$=-\left(\frac{2}{3}\right)\left(\frac{9}{11}\right)=-(-1)\cdot 1=1$$

In fact, $\,(\pm55)^2=106\pmod {139}$

Added: You didn't need the above, but rather: since $\,106\,$ is a square $\,\pmod {139}\,$ and:

(1) $\,106\neq 0\pmod{139}\,$ ;

(2) $\,\Bbb F_{139}:=\Bbb Z/139\Bbb Z\,$ is a field, then the equation $\,x^2=0\pmod{139}\,$ has one unique solution iff $\,a=0\pmod{139}\,$

From the above, it follows your equation has exactly two different roots.