nonresidues

In number theory, a nonresidue is an integer that is not a quadratic residue. An integer 'a' is a quadratic residue modulo 'n' if there exists an integer 'x' such that x^2 is congruent to 'a' modulo 'n'. If no such 'x' exists, then 'a' is a quadratic nonresidue modulo 'n'. This definition applies when the greatest common divisor of 'a' and 'n' is 1. If gcd(a, n) is not 1, the concept of quadratic residue is sometimes extended, but the standard definition usually requires coprimality.

The concept of nonresidues is particularly important when working with prime moduli. For a prime modulus 'p', an integer 'a' not divisible by 'p' is either a quadratic residue or a quadratic nonresidue modulo 'p'. There are exactly (p-1)/2 quadratic residues and (p-1)/2 quadratic nonresidues modulo 'p' for any odd prime 'p'. The integer 0 is a quadratic residue modulo any n, as 0^2 = 0.

A common tool for determining whether an integer is a quadratic residue or nonresidue modulo a prime 'p' is the Legendre symbol, denoted as (a/p). The Legendre symbol is 1 if 'a' is a quadratic residue modulo 'p' and 'a' is not divisible by 'p', -1 if 'a' is a quadratic nonresidue modulo 'p', and 0 if 'a' is divisible by 'p'. Thus, a nonresidue modulo 'p' is an integer 'a' for which (a/p) = -1.

The study of quadratic residues and nonresidues is fundamental to many areas of number theory, including the theory of quadratic fields and the development of efficient algorithms for primality testing and integer factorization. The distribution of quadratic residues and nonresidues has been a subject of intense study, leading to important results like the law of quadratic reciprocity.