# Quadratic nonresidue

Jump to: navigation, search

## Definition

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.