Quadratic nonresidue

From Number
Revision as of 21:58, 29 May 2010 by Vipul (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
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.