Vtgyjfy

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^2equiv apmod pimplies y^2equiv apmod pimplies (-y)^2equiv apmod pimplies -y$ is also a solution.

Let $z$ be another solution, so $z^2equiv apmod pequiv y^2pmod p$

$implies pmid (z+y)(z-y)implies zequiv pm ypmod p$

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

For the existence of solution for $pge 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^2equiv apmod p$ we get,

$2 ind_gxequiv ind_gapmod{p-1}$ as $phi(p)=p-1$

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

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

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

Suppose that $a$ is not divisible by the odd prime $p$. We show that if the congruence $x^2equiv 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^2equiv apmod{p}$. Then if $x^2equiv apmod{p}$, we have $x^2equiv r^2pmod{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 $xequiv rpmod{p}$ or $xequiv -rpmod{p}$.

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!

When you are working mod $p$, you are actually working in the field $mathbb{Z}/pmathbb{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).

$$x^2=apmod pLongleftrightarrow (-x)^2=apmod p$$

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