= Quadratic nonresidue
{wiki}
= Quadratic non-residue
{synonym}
A nonzero <congruence class> modulo an <odd prime> is a quadratic nonresidue when it is not a square. In the convention of <quadratic residue>, zero belongs to neither class. Thus $3,5,6$ are the <quadratic nonresidues> modulo seven, while $2,6,7,8,10$ are the <quadratic nonresidues> modulo eleven. No <integer> $x$ satisfies $x^2\equiv3\pmod7$, as the complete square map under <quadratic residue> shows.
A <quadratic nonresidue> is not an arithmetic dead end: multiplying by any fixed <quadratic nonresidue> $n$ exchanges the <quadratic residues> and the <quadratic nonresidues>. If $nq$ were a square for a square $q$, division by $q$ would make $n$ a square. Hence $nQ_p$ consists entirely of <quadratic nonresidues>; it has $(p-1)/2$ elements, because multiplication by nonzero $n$ is a <bijection>. It therefore equals the entire other <coset> of the <quadratic residue> <subgroup>. Modulo seven, $3\{1,2,4\}=\{3,6,5\}$.
The product of two <quadratic nonresidues> is consequently a <quadratic residue>: write them as $nq_1,nq_2$ in that same <coset>, and their product is $n^2q_1q_2$, a square. For example, $3\cdot5\equiv1\pmod7$, whereas $2\cdot3\equiv6\pmod7$ remains a <quadratic nonresidue>. The <multiplicativity of the Legendre symbol> packages these rules as ordinary sign multiplication.
Back to article page
