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