nonresidue

A nonresidue, in number theory, is an element that is not a quadratic residue modulo a given modulus. In particular, for a prime p, an integer a is a quadratic nonresidue modulo p if the congruence x^2 ≡ a (mod p) has no solution. An integer that is a square modulo p is called a quadratic residue modulo p.

For a prime p, every nonzero residue modulo p is either a quadratic residue or a nonresidue, and exactly half of the nonzero residues are residues while the other half are nonresidues. The value zero is a special case since 0 ≡ 0^2 mod p, so it is considered a square. The Legendre symbol (a/p) encodes this dichotomy: (a/p) = 1 if a is a residue, -1 if a is a nonresidue, and 0 if a ≡ 0 (mod p). Euler’s criterion states that a^((p−1)/2) ≡ (a/p) (mod p).

Generalizations extend beyond primes. For a modulus n, one speaks of quadratic residues modulo n as numbers a for which x^2 ≡ a (mod n) is solvable. When n is composite, the Jacobi symbol (a/n) can be defined, but (a/n) = 1 does not guarantee that a is a quadratic residue modulo n. The study of residues and nonresidues relates to quadratic reciprocity, the structure of the multiplicative group modulo p, and various algorithms for computing square roots modulo p, constructing primitive roots, and other number-theoretic tasks.