# Determine the number of solutions for quadratic equation modulo prime

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

-
I've changed the $\LaTeX{}$ in your post. You can get the $\equiv$ sign by using \equiv rather than \cong, which gives $\cong$. You get the 'mod 139' in brackets by using \pmod{139}. – Clive Newstead Jan 6 '13 at 14:53

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?

-

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.

-
The problem begins, "Given that 106 is a quadratic residue modulo 139..." Why compute the Legendre symbol? – Gerry Myerson Jan 6 '13 at 15:24
Sorry! I did not see that. I just changed the answer – PAD Jan 6 '13 at 15:31

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

-
The problem begins, "Given that 106 is a quadratic residue mod 139...," so what is the point of calculating the Legendre symbol? – Gerry Myerson Jan 6 '13 at 15:25
Completely missed that part. Thanks, I'll add an explaining note. – DonAntonio Jan 6 '13 at 15:33