My question is as follows:
Show that if $p$ is an odd prime and $a$ is a positive integer not divisible by p, then the congruence $x^2 \equiv a \pmod{p}$ has either no solution or exactly two incongruent solutions.
Now, I can show that the congruence cannot have exactly one solution. Suppose $z$ is a solution. Then $z^2 \equiv (-z)^2 \equiv a \pmod{p}$, and thus, $-z$ is also a solution. If $z \equiv -z \pmod{p}$, then $2z \equiv 0 \pmod{p}$, so it must be that either $p$|$2$ or $p$|$z$. But since $p$ is odd and prime, $p$ cannot divide 2, and if $p$|$z$, then $p$|$z^2$ and so $a \equiv z^2 \equiv 0 \pmod{p}$, which implies $p$|$a$, a contradiction. Thus, $z$ and $-z$ are incongruent modulo p.
Now, if I can show that the congruence has no more than 2 solutions, then I believe the problem is solved. How can I demonstrate this?
Best Answer
Hint $\ $ prime $\,p\mid(x-b)(x+b)\,\Rightarrow\, p\mid x-b\ \,$ or $\,\ p\mid x+b\,$ by uniqueness of prime factorizations (or some equivalent, e.g. Euclid's Lemma).
Alternatively if $\,c\not\equiv \pm b\,$ is a root then $\,(x-b)(x+b) \equiv (x-c)(x+c)$ contra polynomials over a field have unique prime factorizations.
Remark $\ $ More generally over a field (or domain), a nonzero polynomial has no more roots than its degree. See here for one proof.