$p$ is Prime $p \geq 5$ $\implies$ $|\{n^2 \pmod p\mid n \in [0, p-1]\}| = \frac{p+1}{2}$

Question

I'm trying to prove the following claim.

If $p$ is prime then $$|\{n^2 \pmod p\mid n \in [0, p-1]\}| = \frac{p+1}{2}$$

Where do I start? Would a proof by contradiction, contrapositive, or a direct proof be more intuitive than the other?

Thanks.

Answer 1

Idea $$n^2\mod p = (p - n)^2\mod p$$

Answer 2

Clearly, $a^2$ and $b^2$ (wlog $a>b$) give the same residue modulo $p$ iff $$p\mid a^2-b^2 = (a-b)(a+b)\implies p\mid a-b \vee p\mid a+b$$

But since $0<a-b<p$ we must have $p\mid a+b$ so $a+b=p$. So for each $a\ne 0$ we have exactly one $b$ such that $a+b = p$ and thus the conclusion.