# 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

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?

• Let $x$ be a solution. Then you know $x^2 - z^2 \equiv 0 \pmod{p}$. Does that ring a bell? Feb 24, 2014 at 22:53

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.