= Quadratic residue
{title2=$a\equiv x^2\pmod p$}
{wiki}
For an <odd prime> $p$, a nonzero <congruence class> $a$ is a quadratic residue when $a\equiv x^2\pmod p$ for some <integer> $x$. Here \b["quadratic residue" excludes zero]: zero is a <square of a number>, but is neither a <quadratic residue> nor a <quadratic nonresidue> under this convention. Some treatments include zero among <quadratic residues>; the distinction matters when counting them or discussing their <subgroup>.<Quadratic Residue Patterns Modulo a Prime by Keith Conrad>[Keith Conrad, Quadratic Residue Patterns Modulo a Prime, §1, p. 1: nonzero convention and equal counts]{ref}
Modulo seven, squaring the six nonzero <congruence classes> gives
$$
\begin{array}{c|rrrrrr}
x&1&2&3&4&5&6\\\hline
x^2\bmod7&1&4&2&2&4&1
\end{array}
$$
Thus the <set> of <quadratic residues> is $Q_7=\{1,2,4\}$, and the <quadratic nonresidues> are $\{3,5,6\}$. In particular, \b[$x^2\equiv2\pmod7$ has exactly the two solutions $x\equiv3,4\pmod7$]: $3^2=9\equiv2$ and $4^2=16\equiv2$. Modulo eleven the <quadratic residues> are instead $Q_{11}=\{1,3,4,5,9\}$. Two is therefore a <quadratic residue> modulo seven and a <quadratic nonresidue> modulo eleven: being a <quadratic residue> depends on the modulus.
\Image[/quadratic-residue-square-map-fibers.png]
{title=The square map modulo seven and eleven: two inputs in every nonzero square <fiber>}
{description=Each pair $\{x,p-x\}$ maps to one <quadratic residue>. The six nonzero inputs modulo seven give three outputs; the ten modulo eleven give five. The zero <fiber> is the single input zero, and each <quadratic nonresidue> has an empty <fiber>.}
Why do the <square roots> come in pairs? If $x^2\equiv y^2\pmod p$, the <prime number> $p$ divides $(x-y)(x+y)$, so it divides one factor: $y\equiv x$ or $y\equiv-x\pmod p$. For nonzero $x$ these are distinct, because $p$ is an <odd prime>. Every nonempty nonzero <fiber of a function> of $s(x)=x^2$ therefore contains exactly two inputs. Pairing the $p-1$ nonzero <congruence classes> gives exactly $(p-1)/2$ <quadratic residues> and $(p-1)/2$ <quadratic nonresidues>. Including zero gives $(p+1)/2$ different squares, with one rather than two <square roots> for zero.
The <quadratic residues> form a <subgroup> of the <multiplicative group of a finite field> $\mathbb F_p^\times$, with <index of a subgroup> two. Indeed, one is a square, $(u^2)(v^2)=(uv)^2$, and $(u^2)^{-1}=(u^{-1})^2$; the inverses exist because the inputs are nonzero in the <prime field>. Equivalently, the squaring <group homomorphism> has <kernel of a group homomorphism> $\{1,-1\}$ and <image of a function> $Q_p$. The apparent loss of a sign in squaring becomes a precise division of the nonzero arithmetic into two equal parts.
This structure turns a search for <square roots> into a yes-or-no test: <Euler's criterion> detects <quadratic residues> through <modular exponentiation>, and the <Legendre symbol> records the result as a sign. For a general <integer> modulus, the <modular congruence> $x^2\equiv a\pmod n$ still makes sense, but the two-root count and the <prime field> argument need not survive. For example, $x^2\equiv1\pmod{15}$ has four solutions $1,4,11,14$; the <Chinese remainder theorem> separates the sign choices modulo three and five.
Back to article page
