How many different possible remainders of a square number modulo an odd prime?

Question

Here is a solution to the question:

I get it up to 'This means that either x-y = 0 ...' Beyond that, I am very confused. I was wondering if someone more experienced could clarify the remaining solution/explain it in simpler terms, if that is possible, please? For example:

I don't get what it means when it says:

• We get the same remainder if x and y have the same value mod p
• The only way these can give the same remainder is when they add to a multiple of p...
• This pairs the remainder x with p-x

And so on... Apologies if my question is too vague - I'm just quite stuck on this and would really appreciate any help. Thank you!

Answer 1

Consider a numerical example. $p=5$.

We have

• $4\equiv -1 \pmod 5 \Rightarrow 4^2\equiv (-1)^2 \equiv 1^2 \pmod 5$
• $3\equiv -2 \pmod 5 \Rightarrow 3^2\equiv (-2)^2 \equiv 2^2 \pmod 5$
• $5\equiv 0 \pmod 5\Rightarrow 5^2\equiv 0 \pmod 5$

The primitive remainders modulo $p$ are $\{ 0,1,2,3,\ldots,p-2,p-1 \}$ which are also $\{ 0,1,2,3,\ldots,-2,-1 \}$ modulo $p$. These are $p$ in total.

Squaring these we obtain distinct remainders $\{ 0,1^2,2^2,3^2,\ldots,(\frac{p-1}{2})^2 \} $ modulo $p$.

Thus we obtain $\frac{p-1}{2}$ pairs $\{(1,p-1), (2,p-2), \ldots\}$ (each pair summing to $p$) and a single distinct remainder, $0$.