0
$\begingroup$

Show that $x^2+x+23\equiv 0\mod 173$ has a solution $\iff$ the legendre symbol $\left(\frac{28}{173}\right) = 1$

How can I determine this? I dont see the relation between the legendere symbol (specifically of $\left(\frac{28}{173}\right)$ to this equation

$\endgroup$
  • 1
    $\begingroup$ Check the source, please. It is all about the discriminant, but I got $$D=b^2-4ac=1^2-4\cdot23=-91\equiv 82\pmod{173}.$$ May be $2$ and $8$ traded places? Another formula would make $D/4$ appear, but try as I may I won't see $\sqrt{28}$ come up. $\endgroup$ – Jyrki Lahtonen Nov 23 '16 at 11:54
  • $\begingroup$ The quadratic formular to solve an quadratic equation works in any field of characteristic not equal to $2$. So you just compute the solutions and notice that $\sqrt{28}$ occurs..Edit: I have not checked it. So $\sqrt{82}$ should occur.. $\endgroup$ – MooS Nov 23 '16 at 11:54
0
$\begingroup$

As Jyrki Lahtonen noted in comments, it's likely that intended problem had an $82$ instead of a $28$ in the Legendre symbol. That's because the usual approach has

$$\begin{align} x^2+x+23\equiv0\mod173&\iff4x^2+4x+92\equiv0\mod173\\ &\iff(2x+1)^2+91\equiv0\mod173\\ &\iff(2x+1)^2\equiv-91\equiv82\mod173\\ &\iff\left(82\over173\right)=1 \end{align}$$

Note also that $\left(28\over173\right)=1$ is a slightly weird assertion to make in a setting like this: Since $28$ is $7$ times a square, why not just ask for a proof that the congruence has a solution if and only if $\left(7\over173\right)=1$?

Nonetheless, we can complete the proof of the problem as given simply by proving that $\left(28\over173\right)=\left(82\over173\right)$. We can do this in various ways. One of them, invoking quadratic reciprocity and the fact that $\left(-1\over173\right)=1$ since $173\equiv1$ mod $4$, is as follows:

$$\begin{align} \left(28\over173\right)=\left(82\over173\right)&\iff\left(7\over173\right)=\left(-91\over173\right)\\ &\iff\left(7\over173\right)=\left(7\over173\right)\left(13\over173\right)\\ &\iff1=\left(13\over173\right)\\ &\iff1=\left(173\over13\right)\quad\text{(by quadratic reciprocity)}\\ &\iff1=\left(4\over13\right) \end{align}$$

The last line is true since $4$ is a square.

Note, none of this tells us whether the congruence $x^2+2+23\equiv0$ mod $173$ has a solution, but that's not what the problem asks. (It turns out the congruence doesn't have a solution: $\left(7\over173\right)=\left(173\over7\right)=\left(5\over7\right)=-1$, using reciprocity in the first step and the small size of $7$ in the final step.)

$\endgroup$
0
$\begingroup$

COMMENT.-$28$ is not a quadratic residue modulo $173$. One has applying quadratic reciprocity law and complementary formula $\left(\dfrac{2}{p}\right)=(-1)^{\frac{p^2-1}{8}}$ as usual $$\left(\dfrac{28}{173}\right)=\left(\dfrac{4}{173}\right)\left(\dfrac{7}{173}\right)=\left(\dfrac{7}{173}\right)$$ $$\left(\dfrac{173}{7}\right)\left(\dfrac{7}{173}\right)=(-1)^{258}\left(\dfrac{173}{7}\right)=\left(\dfrac{5}{7}\right)=(-1)^{12}\left(\dfrac{7}{5}\right)=\left(\dfrac{2}{5}\right)=-1$$ Consequently the true fact is to prove $x^2+x+23\equiv 0\mod 173$ has no solution using the fact that $28$ is not quadratic residue modulo 173. (It does not escape me that logically this is equivalent but it is pertinent to say the posted quadratic equation has no solution).

ANSWER.-$x^2+x+23=0$ has no solution in $\Bbb F_{173}$. In fact we can apply the quadratic formula in characteristic not equal to $2$ and this equation has exactly two roots (if not in $\Bbb F_{173}$ then in a quadratic extension of it). One has $$2x=-1\pm\sqrt{-91}=-1\pm\sqrt{82}$$ ►Is it $82$ a quadratic residue modulo $173$$\large?$

$$\left(\frac{82}{173}\right)=\left(\frac{2}{173}\right)\left(\frac{41}{173}\right)$$ Rutinary calculation (see COMMENT) gives $\left(\frac{41}{173}\right)=1$ and $\left(\frac{2}{173}\right)=(-1)^{\frac{29928}{8}}=(-1)^{3741}=-1$. Consequently $$\left(\frac{82}{173}\right)=-1\qquad(*)$$ Thus the equation has no solution in $\Bbb F_{173}$.

Consider now $\left(\frac{28}{173}\right)$. We have by $(*)$ $$\left(\frac{82}{173}\right)\left(\frac{28}{173}\right)=\begin{cases}1\text{ if} \left(\frac{28}{173}\right)=-1\\-1\text{ if }\left(\frac{28}{173}\right)=1\end{cases}$$ We see how it is used $28$ here (it could be replace by many other numbers namely non quadratic residues modulo $173$).

$\endgroup$

Your Answer

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

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