Let $p$ be a prime and $a \in \Bbb Z$, how to prove that the congruence $x^2 \equiv a \pmod p$ has at most two solutions $\bmod p$? I have no idea how to start. Can anyone help me please?

  • $\begingroup$ $x^2=a \Rightarrow x^2-a=0=(x-a)(x+a)$ $\endgroup$ – EA304GT Nov 13 '15 at 1:01

Hint: If $u$ and $v$ are solutions of $x^2 \equiv a \bmod p$, then $p$ divides $u^2-a$ and $v^2-a$ and so divides their difference, $u^2-v^2=(u+v)(u-v)$.

Can you take it from here? If not, see the solution below.

Since $p$ is prime, it must divide one of the factors. This means that $u \equiv \pm v \bmod p$, and so there are at most $2$ solutions.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.