2
$\begingroup$

My question is as follows:

Show that if $p$ is an odd prime and $a$ is a positive integer not divisible by p, then the congruence $x^2 \equiv a \pmod{p}$ has either no solution or exactly two incongruent solutions.

Now, I can show that the congruence cannot have exactly one solution. Suppose $z$ is a solution. Then $z^2 \equiv (-z)^2 \equiv a \pmod{p}$, and thus, $-z$ is also a solution. If $z \equiv -z \pmod{p}$, then $2z \equiv 0 \pmod{p}$, so it must be that either $p$|$2$ or $p$|$z$. But since $p$ is odd and prime, $p$ cannot divide 2, and if $p$|$z$, then $p$|$z^2$ and so $a \equiv z^2 \equiv 0 \pmod{p}$, which implies $p$|$a$, a contradiction. Thus, $z$ and $-z$ are incongruent modulo p.

Now, if I can show that the congruence has no more than 2 solutions, then I believe the problem is solved. How can I demonstrate this?

$\endgroup$
1
  • $\begingroup$ Let $x$ be a solution. Then you know $x^2 - z^2 \equiv 0 \pmod{p}$. Does that ring a bell? $\endgroup$ Feb 24, 2014 at 22:53

1 Answer 1

1
$\begingroup$

Hint $\ $ prime $\,p\mid(x-b)(x+b)\,\Rightarrow\, p\mid x-b\ \,$ or $\,\ p\mid x+b\,$ by uniqueness of prime factorizations (or some equivalent, e.g. Euclid's Lemma).

Alternatively if $\,c\not\equiv \pm b\,$ is a root then $\,(x-b)(x+b) \equiv (x-c)(x+c)$ contra polynomials over a field have unique prime factorizations.

Remark $\ $ More generally over a field (or domain), a nonzero polynomial has no more roots than its degree. See here for one proof.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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