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.

How to show that $x^2 \equiv 23 \equiv 5 \pmod 9$(2) is not solvable? I got that $x^2≡23≡2 (mod 3)$(1) solution would be $x \equiv \pm 2^{\frac{3+1}{4}}\equiv\pm2(mod 3)$ because $3\equiv3 (mod 4)$(3), but because by Euler's criterion $(2/3)\equiv2^{\frac{3-1}{2}}\equiv2\equiv-1(mod 3)$( that is $(2/3)=-1$, so (1) has not solution and so because $x^2 \equiv 23 \equiv 5 \pmod 9 \Leftrightarrow x^2 \equiv 23 \equiv 2 \pmod 3$(5) then also (2) has not solution. Is this correct. I do not know where in wikipedia you get this result(3)( It is Lemma in my lecture notes). And you can't know by using Jacobi symbol $ (\frac{23}{9}) =(\frac{23}{3})^2 =1$. So you cannot by combuting symbol know whether (2) is solvable or not. Can you give some elegant or acceptable solution? And by the way I'm not sure whether (5) is correct analysis and where in wikipedia it can be found( again I find this principle in my lecture notes as Lemma)

share|improve this question
2  
Overkill! If there were a solution $x$, then as you point out $x^2\equiv 2\pmod{3}$. If $x\equiv 0\pmod{3}$, then $x^2\equiv 0\pmod{3}$. If $x\equiv \pm 1\pmod{3}$, then $x^2\equiv 1\pmod{3}$. So we can't have $x^2\equiv 2\pmod{3}$. –  André Nicolas Jun 6 '13 at 21:38
    
Yes, but second interest for me is to know that can you make analysis (5), because I think you cannot of course examine again another $x^2 \equiv 23 \equiv 2 \pmod 3$, because it is repeating same equation. But for example for $x^2 ≡23≡5(mod10)⇔x^2 ≡23≡3(mod5), x^2 ≡23≡1(mod2)$ would be correct to solve. Am I right? –  laovultai Jun 6 '13 at 21:43
    
I don't understand the comment. For example, certainly $23$ is not congruent to $5$ modulo $10$. –  André Nicolas Jun 6 '13 at 21:45
    
I mean that if you try to solve(1) it is equivalent to solve (2) and (3): $x^2 ≡23≡3(mod10)(1)⇔x^2 ≡23≡3(mod5)(2),x^2 ≡23≡1(mod2)(3)$? –  laovultai Jun 6 '13 at 22:00
    
Yes, it is equivalent. If $m$ and $n$ are relatively prime then solving $x^2\equiv a\pmod{mn}$ is equivalent (via the Chinese Remainder Theorem) to solving $x^2\equiv a \pmod{m}$ and also $x^2\equiv a\pmod{n}$. Note that $x^2\equiv 3\pmod{5}$ has no solutions, so $x^2\equiv 3\pmod{10}$ has no solutions. –  André Nicolas Jun 6 '13 at 22:37

2 Answers 2

up vote 3 down vote accepted

Hint: if it had a solution mod $\,9\,$ then that would yield a solution mod $\,3,\,$ which do not exist, i.e. $\ 9\mid x^2-23\,\Rightarrow\,3\mid x^2-2,\,$ but $\,{\rm mod}\ 3\!: x^2\in \{0,\pm1\}^2 \equiv \{0,1\} \not\ni 2.$

share|improve this answer

$0 \times 0 = 0 \mod 9$
$1 \times 1 = 1 \mod 9$
$2 \times 2 = 4 \mod 9$
$3 \times 3 = 0 \mod 9$
$4 \times 4 = 7 \mod 9$
$5 \times 5 = 7 \mod 9$
$6 \times 6 = 0 \mod 9$
$7 \times 7 = 4 \mod 9$
$8 \times 8 = 1 \mod 9$

None of these squares is equal to 5.

share|improve this answer
1  
+1, though it gets messy as the modulo gets larger... –  Pedro Tamaroff Jun 6 '13 at 21:47
    
Following reduction is obvious $0^2\equiv0,(\pm1)^2\equiv1, (\pm2)^2\equiv4, (\pm3)^2\equiv0, (\pm4)^2\equiv7\pmod 9$ –  lab bhattacharjee Jun 8 '13 at 4:46

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.