Prime number and divisibility

Question

Let $p$ be prime, prove that for any integer $r$, there at most $2$ solutions to the equation $x^2-r \equiv 0\pmod p$.

I don't understand the question as if $p=2$, and $r$ odd, then $x^2$ will need to be odd, and we have an infinite number of solutions.

Maybe this is true for $p>2$, but I don't really know how to prove it.

Answer 1

If $a$ and $x$ are solutions of $x^2 \equiv r \pmod p,$

then $x^2 - r \equiv x^2 - a^2 = (x-a)(x+a) \equiv 0 \pmod p$.

Since $p$ is prime, $p | (x-a)(x+a)$ means $p | (x-a)$ or $p | (x+a)$, i.e., $x \equiv a$ or $-a \pmod p$.

Thus, there can be at most two solutions.

Answer 2

$x^2 \equiv r \pmod p$ and $0\le x < p$

$y^2 \equiv r \pmod p$ so that $y\ne x$ and $0 \le y < p$

$x^2 - y^2 \equiv 0 \pmod p$

$(x+y)(x-y) \equiv 0 \pmod p$.

Now $x \ne y $ so $x-y \ne 0$ and $|x-y| < p$ so $p\not \mid x-y$ hence $p|(x+y)$ but $0 < x+y < 2p$ so $x + y= p$

Now if we had a third option so that

$z^2 \equiv r \pmod p$ and $0 \le z <p$ but $z \ne x; z \ne y; x\ne y$ we could use the exact same argument to conclude:

$x+y = x+z = y+z = p$. But that would imply $z = y$ (and $y = x$ and $x = z$).

So $2$ distinct solutions is a possibility (but not a certainty!) but three distinct solutions is not.

(Bear in mind it's possible that there are no solutions.)

(Also not if $x$ is one solution then so is $p-x$ and if $p$ is odd then $x$ and $p-x$ are two distinct solutions. But that does not mean there is a solution at all.)

Answer 3

The integers mod $p$ are a field.

In general, a polynomial of degree $n$ over a field has at most $n$ roots in the field.

Here $n=2.$