Quadratic Residues Proof

Question

This is a problem that came up on my recent exam and have not been able to solve:

Let $p$ be an odd prime and $a \in \mathbb{Z}$ with $p \nmid a$. Show that if $x^2 \equiv a$ (mod $p$) has a solution, then it has exactly two solutions.

After doing some independent research of my own, I found out that this question is related to the topic of quadratic residues and this topic was not covered during lecture prior to being tested. In any case, to approach this question, I would begin by letting $s$ be a solution and then show from there that there exists exactly two. Thus, we have

$s^2 \equiv a$ (mod $p$)

Additionally, we can say that $-s$ is also another solution since when we square this term, we get $s^2$ on the LHS of the congruence. So, if this is the case, then

If $s \equiv -s$ (mod $p$) $\implies$ $2s \equiv 0$ (mod $p$). Then, $p | s$ since $p$ is an odd prime...

Where do I go from here? Im assuming we would get a contradiction of some sort, but don't know how to proceed any further.

Answer 1

Like you said, if $s$ is a solution, then so is $-s$. We also know that since $p \nmid a$, that $s \not\equiv 0 \pmod p$, and so $s$ and $-s$ are distinct solutions, and so there are at least two solutions.

Now note that if $x$ is a solution, then we have that $$ x^2 \equiv a \equiv s^2 \pmod p, $$ and so $p \mid (x - s)(x + s)$. Since $p$ is prime, this implies that either $p \mid x - s$, or $p \mid x + s$, and so we see that any solution $x$ must be congruent to either $s$ or $-s$ modulo $p$, showing that $s$ and $-s$ are in fact the only solutions.

Answer 2

Let $p$ be an odd prime and $a \in \mathbb{Z}$ with $p \nmid a$. Show that if $x^2 \equiv a$ (mod $p$) has a solution, then it has exactly two solutions [in the least residue system modulo $p$].

If think that's necessary because without those bracketed words, there are infinitely many solutions.

Take for example $p = 7$ and $a = 2$. This should immediately suggest the solution $x = 3$. But then $3, 10, 17, 24, 31, \ldots$ are also solutions, but of these only $x = 3$ satisfies $0 < x < p$.

As you've already realized, $x$ can be negative. So $x = -3$ is also a solution. Obviously $x - (-x) = 2x$, and therefore even, but $p$ is odd. So $-3 + 7 = 4$, and it just so happens that $x = 4$ is also a solution satisfying $0 < x < p$.

So if $x$ is a solution in the residue system, then $p - x$ is also a solution. But you have to show these are the only ones in the residue system. Well, I see Dylan already covered that, so I'll end on that note.