BranchesHistoryHelpLogin
Welcome guest
You're not logged in.
269 users online, thereof 0 logged in

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")

Edit or AddNotationAxiomatic Method

This work was contributed under CC BY-SA 3.0 by:

This work is a derivative of:

(none)

Bibliography (further reading)

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