= Quadratic reciprocity
{wiki}
Quadratic reciprocity compares two questions: is the <prime number> $p$ a <quadratic residue> modulo $q$, and is $q$ a <quadratic residue> modulo $p$? Let $p,q$ be \b[distinct <odd primes>]. In terms of the <Legendre symbol>,
$$
\left(\frac pq\right)\left(\frac qp\right)
=(-1)^{\frac{p-1}{2}\frac{q-1}{2}}.
$$
\b[The two <Legendre symbols> have opposite signs exactly when both <primes> are $3$ modulo $4$; otherwise they are equal.] Their values are nonzero because the <primes> are distinct. Equal signs can mean two <quadratic residues> or two <quadratic nonresidues>: reciprocity compares the answers rather than declaring either answer positive.<NIST Digital Library of Mathematical Functions>[T. M. Apostol, Chapter 27, §27.9, equation 27.9.3: distinct odd prime hypotheses and reciprocity law]{ref}
For a direct computation, the nonzero <quadratic residues> modulo $3,5,7$ are respectively $\{1\}$, $\{1,4\}$, and $\{1,2,4\}$. Squaring just $1,\ldots,(p-1)/2$ suffices because $x$ and $p-x$ have the same square modulo an <odd prime> $p$.
$$
\begin{aligned}
\left(\frac37\right)&=-1,&\qquad \left(\frac73\right)&=\left(\frac13\right)=1,\\
\left(\frac57\right)&=-1,&\qquad \left(\frac75\right)&=\left(\frac25\right)=-1.
\end{aligned}
$$
The pair $3,7$ has a sign flip, whereas $5,7$ has two negative signs. These small <quadratic residue> tables make the distinction tangible.
\Image[/quadratic-reciprocity-small-prime-residues.png]
{title=Small <prime> square-residue tables distinguish opposite and equal <Legendre symbol> signs}
{description=Each row uses half the nonzero inputs; the missing entries are unnecessary. The comparisons $3,7$ and $5,7$ are exact finite examples of <quadratic reciprocity>, not evidence by themselves for every <prime> pair.}
The <first supplementary law for quadratic reciprocity> handles numerator $-1$, and the <second supplementary law for quadratic reciprocity> handles numerator $2$:
$$
\left(\frac{-1}{p}\right)=(-1)^{(p-1)/2},\qquad
\left(\frac2p\right)=(-1)^{(p^2-1)/8}.
$$
For an <odd prime> $p$, $-1$ is a <quadratic residue> exactly when $p\equiv1\pmod4$, while $2$ is a <quadratic residue> exactly when $p\equiv1,7\pmod8$. The remaining odd <congruence classes> modulo $8$, namely $3,5$, make $2$ a <quadratic nonresidue>. These laws fill the cases excluded from swapping distinct <odd primes>.<NIST Digital Library of Mathematical Functions>[T. M. Apostol, Chapter 27, §27.9, equations 27.9.1–27.9.2: supplementary values]{ref}
Back to article page
