1
$\begingroup$

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$ )

5 Answers 5

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).

1
  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!

  • 0
    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.2012-12-07
1

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}$.

0

$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\,$

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)$

  • 0
    @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.2012-12-07