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$ )
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$ )
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).
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$.
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$.
This means that there may be more solutions like $x+p, x+2p, \ldots$, but at most two modulo $p$.
Cheers!
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}$.
$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\,$
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)$