Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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
up vote 3 down vote accepted

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?

share|cite|improve this answer

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.

share|cite|improve this answer
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{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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.