1
$\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$
5
  • 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$ Commented Jun 6, 2013 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
    Commented Jun 6, 2013 at 21:43
  • $\begingroup$ I don't understand the comment. For example, certainly $23$ is not congruent to $5$ modulo $10$. $\endgroup$ Commented Jun 6, 2013 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
    Commented Jun 6, 2013 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$ Commented Jun 6, 2013 at 22:37

2 Answers 2

5
$\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$
2
  • 1
    $\begingroup$ +1, though it gets messy as the modulo gets larger... $\endgroup$
    – Pedro
    Commented Jun 6, 2013 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$ Commented Jun 8, 2013 at 4:46
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$

You must log in to answer this question.