0
$\begingroup$

Let $p$ be an odd prime and $a$ be an integer with $\gcd(a, p) = 1$. Show that $x^2 - a \equiv 0 \mod p$ has either $0$ or $2$ solutions modulo $p$

I am clueless with this one. Hints please.

$\endgroup$

3 Answers 3

2
$\begingroup$

If $x^2-a=0 \mod p$ has some solution $b$, it means that $b^2=a$, and hence you original question becomes

$$x^2-b^2 \equiv 0 \mod p$$

Can you prove now that this equation has exactly two solutions?

$\endgroup$
1
  • 1
    $\begingroup$ when $b\neq -b$ (+1) $\endgroup$
    – Belgi
    Oct 11, 2012 at 3:59
1
$\begingroup$

For $\,p=2\,$ the claim fails, as $\,x^2-1=x^2+1=(x+1)^2=0\pmod 2\,$ has one unique solution.

If $\,p\,$ is odd and $\,x^2-a=0\pmod p\,$ has a solution $\,b\,$, then

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

$$ x=b\pmod p\,\,or\,\,x=-b\pmod p$$

And now you only have to justify why the two solutions above are actually different.

$\endgroup$
0
$\begingroup$

Hint $\ $ In a field, $\rm\ x_2^2 = x_1^2 \iff 0 = x_2^2-x_1^2 = (x_2\!-x_1\!)\,(x_2\!+x_1\!)\iff x_2 = \pm\, x_1$

Remark $\ $ Generally a nonzero polynomial over a domain has no more roots than its degree.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .