Least quadratic nonresidue
ID: least-quadratic-nonresidue
For an odd prime , the least quadratic nonresidue is the smallest positive integer whose nonzero residue class is a quadratic nonresidue modulo . For example, the nonzero quadratic residues modulo seven are , so .
The least quadratic nonresidue is itself a prime number. Otherwise it has a factorization with . By minimality, both residue classes are quadratic residues, so and would give , a contradiction. This illustrates why multiplicative information can constrain a least exceptional integer.
New to topics? Read the docs here!