0
$\begingroup$

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)

$\endgroup$
  • 2
    $\begingroup$ 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}$. $\endgroup$ – André Nicolas Jun 6 '13 at 21:38
  • $\begingroup$ 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? $\endgroup$ – user2723 Jun 6 '13 at 21:43
  • $\begingroup$ I don't understand the comment. For example, certainly $23$ is not congruent to $5$ modulo $10$. $\endgroup$ – André Nicolas Jun 6 '13 at 21:45
  • $\begingroup$ 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)$? $\endgroup$ – user2723 Jun 6 '13 at 22:00
  • $\begingroup$ 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. $\endgroup$ – André Nicolas Jun 6 '13 at 22:37
2
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy