Editing Quadratic residue (section)

===Prime modulus===

Modulo 2, every integer is a quadratic residue.

Modulo an odd [[prime number]] ''p'' there are (''p'' + 1)/2 residues (including 0) and (''p'' &minus; 1)/2 nonresidues, by [[Euler's criterion]]. In this case, it is customary to consider 0 as a special case and work within the [[Multiplicative group of integers modulo n|multiplicative group of nonzero elements]] of the [[Field (mathematics)|field]] <math>(\mathbb{Z}/p\mathbb{Z})</math>. In other words, every congruence class except zero modulo ''p'' has a multiplicative inverse. This is not true for composite moduli.<ref name="Gauss, DA, art. 96">Gauss, DA, art. 96</ref>

Following this convention, the multiplicative inverse of a residue is a residue, and the inverse of a nonresidue is a nonresidue.<ref name="Gauss, DA, art. 98">Gauss, DA, art. 98</ref>

Following this convention, modulo an odd prime number there is an equal number of residues and nonresidues.<ref name="Gauss, DA, art. 96"/>

Modulo a prime, the product of two nonresidues is a residue and the product of a nonresidue and a (nonzero) residue is a nonresidue.<ref name="Gauss, DA, art. 98"/>

The first supplement<ref>Gauss, DA, art 111</ref> to the [[law of quadratic reciprocity]] is that if ''p'' ≡ 1 (mod 4) then &minus;1 is a quadratic residue modulo ''p'', and if ''p'' ≡ 3 (mod 4) then &minus;1 is a nonresidue modulo ''p''. This implies the following:

If ''p'' ≡ 1 (mod 4) the negative of a residue modulo ''p'' is a residue and the negative of a nonresidue is a nonresidue.

If ''p'' ≡ 3 (mod 4) the negative of a residue modulo ''p'' is a nonresidue and the negative of a nonresidue is a residue.