I have found various proofs of this question usig primitive roots, but I want to prove it without using primitive roots!
Here is my question again:
Let $p$ be prime. Prove that there are the same number of quadratic residues modulo p as there are non-residues. Clearly state where you have used that $p$ is prime.
Thanks! :)
We are considering only invertible elements, and we have to assume $p>2$ since for $p=2$ the statament is false because there is just one invertible element. $x^2 \equiv y^2 \pmod p \iff x \equiv y \pmod p$ or $x \equiv -y \pmod p$ because $\mathbb Z_p$ is a field and thus an integral domain. So you reach exactly two times the same quadratic residue using the $p-1$ invertible elements. Thus you get exactly $\frac{p-1}{2}$ different values. The remaining are $(p-1) - \frac{p-1}{2}=\frac{p-1}{2}$.