# Proof

• 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

1. Landau, Edmund: "Vorlesungen über Zahlentheorie, Aus der Elementaren Zahlentheorie", S. Hirzel, Leipzig, 1927