# Modular Arithmetic & Congruences

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?

• I think your theorem, that's it. 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?