In number theory, an integer q is called a quadratic residue modulo n if it is congruent to a perfect square modulo n; i.e., if there exists an integer x such that:
Otherwise, q is called a quadratic nonresidue modulo n.
Originally an abstract mathematical concept from the branch of number theory known as modular arithmetic, quadratic residues are now used in applications ranging from acoustical engineering to cryptography and the factoring of large numbers.
History, conventions, and elementary facts
Fermat, Euler, Lagrange, Legendre, and other number theorists of the 17th and 18th centuries established theorems and formed conjectures 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 states 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 the numbers 0, 1, ..., . Because a2 ≡ (n − a)2 (mod n), the list of squares modulo n is symmetric around n/2, and the list only needs to go that high. This can be seen in the table below.
Thus, the number of quadratic residues modulo n cannot exceed n/2 + 1 (n even) or (n + 1)/2 (n odd).
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 − 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 nonzero elements of the field Z/pZ. (In other words, every congruence class except zero modulo p has a multiplicative inverse. This is not true for composite moduli.)
Following this convention, the multiplicative inverse of a residue is a residue, and the inverse of a nonresidue is a nonresidue.
Following this convention, modulo an odd prime number there are an equal number of residues and nonresidues.
Modulo a prime, the product of two nonresidues is a residue and the product of a nonresidue and a (nonzero) residue is a nonresidue.
The first supplement to the law of quadratic reciprocity is that if p ≡ 1 (mod 4) then −1 is a quadratic residue modulo p, and if p ≡ 3 (mod 4) then −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).
For example, mod (32) the odd squares are
12 ≡ 152 ≡ 1
32 ≡ 132 ≡ 9
52 ≡ 112 ≡ 25
72 ≡ 92 ≡ 49 ≡ 17
and the even ones are
02 ≡ 82 ≡ 162 ≡ 0
22 ≡ 62≡ 102 ≡ 142≡ 4
42 ≡ 122 ≡ 16.
So a nonzero number is a residue mod 8, 16, etc., if and only if it is of the form 4k(8n + 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.
If the modulus is pn, then pka is a residue modulo pn if k ≥ n is a nonresidue modulo pn if k < n is odd is a residue modulo pn if k < n is even and a is a residue is a nonresidue modulo pn if k < n is even and a is a nonresidue.
Notice that the rules are different for powers of two and powers of odd primes.
Modulo an odd prime power n = pk, 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 pk for every prime power dividing n. if a is a nonresidue modulo n, then a is a nonresidue modulo pk 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.