Quadratic nonresidue

From Number
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.