Editing Quadratic residue (section)

==History, conventions, and elementary facts==
[[Fermat]], [[Euler]], [[Joseph Louis Lagrange|Lagrange]], [[Adrien-Marie Legendre|Legendre]], and other number theorists of the 17th and 18th centuries established theorems<ref>Lemmemeyer, Ch. 1</ref> and formed conjectures<ref>Lemmermeyer, pp 6&ndash;8, p. 16 ff</ref> about quadratic residues, but the first systematic treatment is § IV of [[Gauss]]'s ''[[Disquisitiones Arithmeticae]]'' (1801). Article 95 introduces the terminology "quadratic residue" and "quadratic nonresidue", and says that if the context makes it clear, the adjective "quadratic" may be dropped.

For a given ''n'', a list of the quadratic residues modulo ''n'' may be obtained by simply squaring all the numbers 0, 1, ..., {{nowrap|''n'' &minus; 1}}. Since ''a''≡''b'' (mod ''n'') implies ''a''<sup>2</sup>≡''b''<sup>2</sup> (mod ''n''), any other quadratic residue is congruent (mod ''n'') to some in the obtained list. But the obtained list is not composed of mutually incongruent quadratic residues (mod n) only. Since ''a''<sup>2</sup>≡(''n''&minus;''a'')<sup>2</sup> (mod ''n''), the list obtained by squaring all numbers in the list 1, 2, ..., {{nowrap|''n'' &minus; 1}} (or in the list 0, 1, ..., ''n'') is symmetric (mod ''n'') around its midpoint, hence it is actually only needed to square all the numbers in the list 0, 1, ..., <math>\lfloor</math> ''n''/2 <math>\rfloor</math>. The list so obtained may still contain mutually congruent numbers (mod ''n''). Thus, the number of mutually noncongruent quadratic residues modulo ''n'' cannot exceed ''n''/2 + 1 (''n'' even) or (''n'' + 1)/2 (''n'' odd).<ref>Gauss, DA, art. 94</ref>

The product of two residues is always a residue.

===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.

===Prime power modulus===
All odd squares are ≡ 1 (mod 8) and thus also ≡ 1 (mod 4). If ''a'' is an odd number and ''m'' = 8, 16, or some higher power of 2, then ''a'' is a residue modulo ''m'' if and only if ''a'' ≡ 1 (mod 8).<ref>Gauss, DA, art. 103</ref>

<blockquote>For example, mod (32) the odd squares are
:1<sup>2</sup> &equiv; 15<sup>2</sup> &equiv; 1
:3<sup>2</sup> &equiv; 13<sup>2</sup> &equiv; 9
:5<sup>2</sup> &equiv; 11<sup>2</sup> &equiv; 25
:7<sup>2</sup> &equiv; 9<sup>2</sup>  &equiv; 49 &equiv; 17

and the even ones are
:0<sup>2</sup> &equiv; 8<sup>2</sup> &equiv; 16<sup>2</sup> &equiv; 0
:2<sup>2</sup> &equiv; 6<sup>2</sup>&equiv; 10<sup>2</sup> &equiv; 14<sup>2</sup>&equiv; 4
:4<sup>2</sup> &equiv; 12<sup>2</sup> &equiv; 16.

</blockquote>

So a nonzero number is a residue mod 8, 16, etc., if and only if it is of the form 4<sup>''k''</sup>(8''n'' + 1).

A number ''a'' relatively prime to an odd prime ''p'' is a residue modulo any power of ''p'' if and only if it is a residue modulo ''p''.<ref name="Gauss, DA, art. 101">Gauss, DA, art. 101</ref>

If the modulus is ''p''<sup>''n''</sup>,
:then ''p''<sup>''k''</sup>''a''
::is a residue modulo ''p''<sup>''n''</sup> if ''k'' &ge; ''n''
::is a nonresidue modulo ''p''<sup>''n''</sup> if ''k'' &lt; ''n'' is odd
::is a residue modulo ''p''<sup>''n''</sup> if ''k'' &lt; ''n'' is even and ''a'' is a residue
::is a nonresidue modulo ''p''<sup>''n''</sup> if ''k'' &lt; ''n'' is even and ''a'' is a nonresidue.<ref>Gauss, DA, art. 102</ref>

Notice that the rules are different for powers of two and powers of odd primes.

Modulo an odd prime power ''n'' = ''p''<sup>''k''</sup>, the products of residues and nonresidues relatively prime to ''p'' obey the same rules as they do mod ''p''; ''p'' is a nonresidue, and in general all the residues and nonresidues obey the same rules, except that the products will be zero if the power of ''p'' in the product ≥ ''n''.

Modulo 8, the product of the nonresidues 3 and 5 is the nonresidue 7, and likewise for permutations of 3, 5 and 7. In fact, the multiplicative group of the non-residues and 1 form the [[Klein four-group]].

===Composite modulus not a prime power===

The basic fact in this case is
:if ''a'' is a residue modulo ''n'', then ''a'' is a residue modulo ''p''<sup>''k''</sup> for ''every'' prime power dividing ''n''.
:if ''a'' is a nonresidue modulo ''n'', then ''a'' is a nonresidue modulo ''p''<sup>''k''</sup> for ''at least one'' prime power dividing ''n''.

Modulo a composite number, the product of two residues is a residue. The product of a residue and a nonresidue may be a residue, a nonresidue, or zero.

<blockquote>
For example, from the table for modulus 6 &nbsp; 
 '''1''', 2, '''3''', '''4''', 5 (residues in '''bold''').

The product of the residue 3 and the nonresidue 5 is the residue 3, whereas the product of the residue 4 and the nonresidue 2 is the nonresidue 2.

</blockquote>

Also, the product of two nonresidues may be either a residue, a nonresidue, or zero.

<blockquote>
For example, from the table for modulus 15 &nbsp; 
 '''1''', 2, 3, '''4''', 5, '''6''', 7, 8,  '''9''', '''10''', 11, 12, 13, 14 (residues in '''bold''').

The product of the nonresidues 2 and 8 is the residue 1, whereas the product of the nonresidues 2 and 7 is the nonresidue 14.

</blockquote>

This phenomenon can best be described using the vocabulary of abstract algebra. The congruence classes relatively prime to the modulus are a [[Group (mathematics)|group]] under multiplication, called the [[group of units]] of the [[Ring (mathematics)|ring]] <math>(\mathbb{Z}/n\mathbb{Z})</math>, and the squares are a [[subgroup]] of it. Different nonresidues may belong to different [[coset]]s, and there is no simple rule that predicts which one their product will be in. Modulo a prime, there is only the subgroup of squares and a single coset.

The fact that, e.g., modulo 15 the product of the nonresidues 3 and 5, or of the nonresidue 5 and the residue 9, or the two residues 9 and 10 are all zero comes from working in the full ring <math>(\mathbb{Z}/n\mathbb{Z})</math>, which has [[zero divisor]]s for composite ''n''.

For this reason some authors<ref>e.g., {{harvnb|Ireland|Rosen|1990|p=50}}</ref> add to the definition that a quadratic residue ''a'' must not only be a square but must also be [[relatively prime]] to the modulus ''n''. (''a'' is coprime to ''n'' if and only if ''a''<sup>2</sup> is coprime to ''n''.)

Although it makes things tidier, this article does not insist that residues must be coprime to the modulus.