Question

Show that if p is an odd prime and a is an integer not divisible by p, then the congruence $x^2\equiv a(modp)$has either no solutions or exactly two incongruent solutions modulo p.

Short answer

If p is an odd prime and a is an integer not divisible by p, then the congruence $x^2\equiv a(modp)$has either no solutions or exactly two incongruent solutions modulo p.

Step-by-step solution

Step: 1

Assume that s is a solution of $x^2\equiv a(modp)$

Then because $(-s{)}^2=s^2$is also a solution.

Furthermore, $s\ne -s(modp)$. Otherwise, p|2s. Which implies that p/s, and this

implies, using the original assumption, that $p\mid a$, which is a contradiction.

Step: 2

Furthermore, if s and t are incongruent solutions modulo p then because

$\begin{array}{r}{s}^2\equiv t^2(modp)\\ p\mid s^2-t^2\\ \Rightarrow p\mid (s+t)(s-t)\end{array}$

Step: 3

We have $p\mid s-t$

$s\equiv t(modp)\text{or}s\equiv -t(modp)$

Hence there are at most two solutions.