Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

5 Answers 5

up vote 0 down vote accepted

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

share|improve this answer
    
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!

share|improve this answer
    
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\,$

share|improve this answer

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

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.