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

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.

• I don't want to be nit picky but $p=2$ is definitely a counter example – Stan Tendijck Feb 20 at 18:29
• @StanTendijck the title does state that $p≥5$ but this seems to have been lost within the actual question... – Benjamin Feb 20 at 19:00

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 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.
Idea $$n^2\mod p = (p - n)^2\mod p$$
• I notice when I let $n = p-1$ that its the same as when $n=1$. Similarly for $n = p-k$ is equal to when $n = k$, but I'm not quite sure how to write this mathematically, or if I'm even on the right track. Intuitively I notice that the squares repeat halfway through with the exception of $0$, so that's why there are $\frac{p+1}{2}$ unique squares. But I'm still a bit confused. – jd94 Feb 20 at 19:23