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

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

• 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. – Jyrki Lahtonen Nov 23 '16 at 11:54
• 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.. – MooS Nov 23 '16 at 11:54

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

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