Show that if $p$ is an odd prime and $a \in \mathbb Z$ such that $p$ doesn't divide $a$ then $x^2\equiv a(mod p)$ has no solutions or exactly 2 incongruent solutions.

The only theorem that I thought could help was:

Let $a, b$ and $m$ be integers with $m > 0$ and $gcd(a,m)=d$. If $ d $ doesn't divides $b$ then $ax\equiv b(mod p)$ has no solutions. If $d$ divides $b$ then $ax\equiv b(mod p)$ has exactly $d$ incongruent solutions modulo $m$.

But I feel that this would be an invalid theorem for this proof since $ax$ and $x^2$ are of different degrees.

Thoughts? Other methods to approach this?

  • $\begingroup$ I think your theorem, that's it. $\endgroup$ Jun 3 '13 at 9:40

If $x^2\equiv a\pmod p, (-x)^2\equiv a\pmod p$

So, if $x$ is a solution, so will be $-x$

If $z$ is a solution, then $z^2\equiv a\pmod p\implies z^2\equiv x^2\implies p$ divides $(z-x)(z+x)$

If $p$ divides both $z-x,z+x,$ then $2x=(z+x)+(z-x)$ will be divisible by $p\implies p$ will divide $x$ if $p$ is odd.

But as $(a,p)=1, p$ can not divide $x$

So, either $p$ divides $z-x,z\equiv x\pmod p$

or $p$ divides $z+x, z\equiv-x\pmod p$

So, there can not be more than two in-congruent solutions $\pmod p,$

Now, as there are $p-1$ in-congruent numbers $\pmod p,$ there are exactly $\frac{p-1}2$ Quadratic residues of $p$ and $(p-1)-\frac{p-1}2=\frac{p-1}2$ Non-residues


Hints: Suppose $x^2 \equiv a \pmod p$, how about $(-x)^2$?

Suppose $x^2\equiv y^2 \pmod p$, then $x^2-y^2 = (x-y)(x+y) \equiv 0 \pmod p$. What can you conclude about $x$ and $y$ knowing that $p$ is prime?


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.