Quadratic nonresidue

Definition

Suppose $n$ is a natural number. A quadratic nonresidue modulo $n$ is a number $a$ (or a residue class of a number $a$) relatively prime to $n$ such that the equation:

$x^2\equiv a(\mathrm{mod}n)$

has no solution. Since $a$ is relatively prime to $n$, it suffices to check that there is no solution with $x$ relatively prime to $n$. Further, it suffices to check that there is no solution for $x$ relatively prime to $n$ and $0\le x\le n$.

Note that the term quadratic nonresidue is used both for actual numbers and for residue classes. The term is not used in cases where $a$ is not relatively prime to $n$.

The opposite of quadratic nonresidue is quadratic residue.