0

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.

amWhy
  • 209,954
Student number x
  • 355
  • 4
    They mean solutions $\pmod p$. Thus, if $p=7$ and $r=2$ the only solutions would be $3,4$. For $p=2, r=1$ the only solution is $x=1$. – lulu Jan 06 '19 at 17:06
  • makes more sense! thank you - do you have any idea how to prove it though? – Student number x Jan 06 '19 at 17:17
  • The mean solutions modulo $p$. There are only $p$ classes. If $p=2$ then are two possible $x$, $0$ and $1$. Any other odd number is $\equiv 2 \pmod 2$. – fleablood Jan 06 '19 at 17:53
  • ..... if $p = 2$ and $r=7$ then there is one solution mod $2$. $1^2 - 7\equiv 0 \pmod 2$ but $0^2 - 7 \not \equiv 0 \pmod 2$. Any other odd number,say $253$ so that $253^2 - 7 \equiv 0 \pmod 2$ is the same solution as $253 \equiv 1 \pmod 2$. In the $\mod 2$ system $253$ and $1$ are the same class $253 \equiv 1$. So $1$ is the only solution. – fleablood Jan 06 '19 at 17:58
  • For the record, If $x^2 \equiv r \pmod p$ then $(kp+x)\equiv r \pmod p$ so if there are any integer solutions there are an infinite number of INTEGER solutions, but we are not asking for integers solution but EQUIVALENCE solutions. $kp + x \equiv x$ so they are the SAME solution. It's only one, even though ther are an infinite number of integers that are all EQUIVALENT to the one solution. – fleablood Jan 06 '19 at 18:16
  • Cf. this question – J. W. Tanner Jan 07 '19 at 18:49

3 Answers3

1

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

J. W. Tanner
  • 60,406
  • 1
    Do you think this question is being at a level where the student can be expected to prove that a polynomial of degree $n$ has at most $n$ solutions? Or to take it as a given? – fleablood Jan 06 '19 at 18:57
  • But +1 for bringing in ideas about what the question is actually asking and considering consequences. – fleablood Jan 06 '19 at 18:58
  • I provided another answer, which is less abstract – J. W. Tanner Jan 06 '19 at 19:18
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.

J. W. Tanner
  • 60,406
  • As noted by others, it is possible there are no solutions. For example $x^2 - 2 \equiv 0 \pmod 3$ has no solutions. – J. W. Tanner Jan 07 '19 at 18:57
0

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

fleablood
  • 124,253