Suppose is a natural number. A quadratic nonresidue modulo is a number (or a residue class of a number ) relatively prime to such that the equation:
has no solution. Since is relatively prime to , it suffices to check that there is no solution with relatively prime to . Further, it suffices to check that there is no solution for relatively prime to and .
Note that the term quadratic nonresidue is used both for actual numbers and for residue classes. The term is not used in cases where is not relatively prime to .
The opposite of quadratic nonresidue is quadratic residue.