# How to prove that the number of solutions of $x^2 \equiv a \pmod{p}$ is 0 or 2?

I want to prove that the equation $x^2 \equiv a \pmod{p}$ either doesn't have or has 2 solutions.

(p is odd prime , a is integer , a $\ne pk$ )

-

If $y$ is a solution of $x^2\equiv a\pmod p\implies y^2\equiv a\pmod p\implies (-y)^2\equiv a\pmod p\implies -y$ is also a solution.

Let $z$ be another solution, so $z^2\equiv a\pmod p\equiv y^2\pmod p$

$\implies p\mid (z+y)(z-y)\implies z\equiv \pm y\pmod p$

So if there is a solution, there will be exactly one more.

For the existence of solution for $p\ge 3$, we can try in the following way:

if $g$ is a primitive root of $p,$ taking discrete logarithm with respect to $g$ on $x^2\equiv a\pmod p$ we get,

$2 ind_gx\equiv ind_ga\pmod{p-1}$ as $\phi(p)=p-1$

As $p-1$ is even and $ind_gx$ must be some integer $\in[0,p-1],$

$ind_gx\equiv \frac{ind_ga}2\pmod{\frac{p-1}2}\implies ind_ga$ must be even to admit any solution.

For example, if $a\equiv-1\pmod p, ind_ga=\frac{p-1}2 \implies 4\mid (p-1)$

-
can you show me how to i prove that $x^2 \equiv a$ hasn't solution? – World Dec 7 '12 at 17:45
@World, please find the edited answer. – lab bhattacharjee Dec 7 '12 at 18:01
when we haven't solution? I don't understand. – World Dec 7 '12 at 18:18
@World, we need to identify a primitive root$g$ of $p$, the previous always exists for a prime, then find the index of $a$ with respect to $g\pmod p,$ which must be even to admit any solution. – lab bhattacharjee Dec 7 '12 at 18:22
1. If there is solution, then there is a second (different). Observe that $$(p-x)^2 = x^2 - 2px + p^2,$$ so $$(p-x)^2 = x^2 \pmod p.$$ Now assume that $x = p-x$, then $p = 2x$ and $p$ would be even (contradiction), so $x \neq p-x$.

2. There are at most two different solutions modulo $p$. Let $x^2 = a \pmod p$ and $y^2 = a \pmod p$ then $$x^2 - y^2 = 0 \pmod p,$$ $$(x+y)(x-y) = 0 \pmod p,$$ that is $y = x \pmod p$ or $y = -x \pmod p$.

3. This means that there may be more solutions like $x+p, x+2p, \ldots$, but at most two modulo $p$.

Cheers!

-
Thanks. what is mean $p-x \ne x$ .can you explain more about this. – World Dec 7 '12 at 17:51
We proved that there is possibly a second solution. The problem is, what if the two solutions $x$ and $p-x$ coincide, i.e. $x = p-x$ (we would have only one solution then)? However, this would imply that $p$ is even and contradict the assumption that $p$ is odd, therefore it is impossible that $x = p - x$ and therefore $x \neq p - x$. Also, $a \neq 0 \pmod p$, so $x$ does not divide $p$ and therefore we have at least two different solutions. – dtldarek Dec 7 '12 at 18:22

$$x^2=a\pmod p\Longleftrightarrow (-x)^2=a\pmod p$$

and since $\,p\,$ is an odd prime, $\,x\neq -x\,$ whenever $\,x\neq 0\,$

-

When you are working mod $p$, you are actually working in the field $\mathbb{Z}/p\mathbb{Z} = \mathbb{F}_p$. So, your statement translates to whether a polynomial of degree $2$ has roots in $\mathbb{F}_p$ (which is not guaranteed because $\mathbb{F}_p$ is not algebraically closed), and if it does have a root, how many roots can it have in total (namely $2$, because any quadratic polynomial has at most $2$ roots in any field, and if one root of a quadratic polynomial is in the field, the other root must also be in the field).

-

Suppose that $a$ is not divisible by the odd prime $p$. We show that if the congruence $x^2\equiv a$ has a solution, then it has exactly two. As shown by DonAntonio and Pambos, if there is a solution then there are at least two.

We show that there are no more than two. Suppose that $r^2\equiv a\pmod{p}$. Then if $x^2\equiv a\pmod{p}$, we have $x^2\equiv r^2\pmod{p}$.

It follows that $p$ divides $x^2-r^2$, that is, $p$ divides $(x-r)(x+r)$. But since $p$ is prime, it follows that $p$ divides $x-r$ or $p$ divides $x+r$. That says that $x\equiv r\pmod{p}$ or $x\equiv -r\pmod{p}$.

-