Proposition: Number of Quadratic Residues in Reduced Residue Systems Modulo a Prime

Let $p > 2$ be a prime number. In every reduced residue system modulo $p$ there are exactly $\frac{p-1}{2}$ quadratic residues modulo $p$ and exactly $\frac{p-1}{2}$ quadratic nonresidues modulo $p.$ Moreover, the $\frac{p-1}{2}$ quadratic residues are represented by the congruence classes modulo $p$ of the integers $1^2,2^2,\ldots,\left(\frac{p-1}{2}\right)^2.$

In particular, for every prime $p > 2,$ the Legendre symbol $\left(\frac{n}{p}\right)$ takes in the interval $1\le n\le p-1$ exactly $\frac{p-1}{2}$ times the value $1$ and exactly $\frac{p-1}{2}$ times the value $-1.$

Proofs: 1

Proofs: 1


Thank you to the contributors under CC BY-SA 4.0!

Github:
bookofproofs


References

Bibliography

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