If $p$ is an odd prime and $a$ is a positive integer not divisible by p, then the congruence has either no solution or 2 incongruent solutions

Question

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?

Answer 1

If $\,b\,$ is a root then $\!\bmod p\!:\ b^2\equiv a\,$ so $\,x^2-a\equiv x^2-b^2\equiv (x\!-\!b)(x\!+\!b),\,$ so if $\,c\,$ is also a root then $\,(c\!-\!b)(c\!+\!b)\equiv 0\,$ so $\,p\mid(c\!-\!b)(c\!+\!b)\,\color{#c00}{\rm \overset{F}\Rightarrow}\, p\mid c\!-\!b\ $ or $\ p\mid c\!+\!b,\,$ so $\,c\equiv \pm b,\,$ by $\rm\color{#c00}{F}$ = FTA = existence & uniqueness of prime factorizations (or by Euclid's Lemma or closely related results).

Or 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 (Euclidean domains are UFDs). See here for more on this view.

Remark $\ $ More generally over a field (or domain) such as $\,\Bbb Q,\Bbb R,\Bbb C,\Bbb Z_p,\,$ iterating the Factor Theorem shows that nonzero polynomial has no more roots than its degree (in fact this property is equivalent to the coefficient ring being a domain, i.e. $\,a,b\neq 0\Rightarrow ab\neq 0).\,$ See here for a proof.