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

Question

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

Answer 1

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

Answer 2

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