Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
2  
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
add comment

3 Answers

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|improve this answer
add comment

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|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
add comment

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

share|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
add comment

Your Answer

 
discard

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.