Proof
(related to Proposition: Number of Quadratic Residues in Reduced Residue Systems Modulo a Prime)
- By hypothesis, $p > 2$ is a prime number and we consider a reduced residue system modulo $p$. Let's call it $R.$
- $R$ can be respresented by the $p-1$ numbers $n=1,\ldots,p-1.$
- Let $n\in R,$ and assume that $n$ is a quadratic residue modulo $p.$
- Since $p\not\mid n,$ there is at least one solution of the congruence $x^2(p)=n(p)$ in $R,$ and, by counting the roots of a diophantine polynomial modulo $p$, there are at most two solutions in $R.$
- Because $(p-x)^2(p)\equiv (-x)^2(p)\equiv x^2(p)$, if $x$ solves the polynomial, so does $p-x.$
- Therefore, $n$ must be congruent to exactly one of the $\frac{p-1}{2}$ numbers in $R$ from the interval $1\le x \le \frac{p-1}{2}.$
- Hence, there are exactly $\frac{p-1}{2}$ quadratic residues modulo $p,$ since the $\frac{p-1}{2}$ numbers $1^2,2^2,\ldots,\left(\frac{p-1}{2}\right)^2$ are all incongruent.
- Since $R$ has $p-1$ elements, $R$ contains $p-1-\frac{p-1}{2}=\frac{p-1}{2}$ quadratic nonresidues modulo $p.$
∎
Thank you to the contributors under CC BY-SA 4.0! 
- Github:
-
References
Bibliography
- Landau, Edmund: "Vorlesungen über Zahlentheorie, Aus der Elementaren Zahlentheorie", S. Hirzel, Leipzig, 1927
