I need a proof for the following:
Suppose that $p$ is an odd prime. If $(a, p) = 1$, then $x^2 = a \pmod p$ either has exactly $2$ solutions or has no solutions within $\textrm{crs}/p$.
I can come up with a lot of examples that work, but I am having trouble with the proof.
If it has a root $\,b^2\equiv a\,$ then $\,0\equiv x^2\!-\!b^2\equiv (x\!-\!b)(x\!+\!b).\,$ Then prime $\,p\mid (x\!-\!b)(x\!+\!b)\,$ so $\,p\mid x\!-\!b\,$ or $\,x\!+\!b,\,$ so $\,x\equiv b\,$ or $\,-b,\,$ and $\,-b\not\equiv b,\,$ else $\, 2b\equiv 0,\,$ contra $\,(p,2)=1=(p,b^2)$
Remark $\ $ More generally a commutative ring $\ne 0$ is an integral domain $(a,b\ne 0\,\Rightarrow, ab\ne 0)$ iff nonzero polynomials over it have no more roots than their degree, as is easily shown via an inductive proof using the Factor Theorem, e.g. see the BiFactor Theorem.