**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.$

| | | | | created: 2019-05-12 20:25:06 | modified: 2019-05-12 20:54:47 | by: *bookofproofs* | references: [1272]

## 1.**Proof**: *(related to "Number of Quadratic Residues in Reduced Residue Systems Modulo a Prime")*

[1272] **Landau, Edmund**: “Vorlesungen über Zahlentheorie, Aus der Elementaren Zahlentheorie”, S. Hirzel, Leipzig, 1927

© 2018 Powered by BooOfProofs, All rights reserved.