Quadratic reciprocity decides whether one odd prime is a square modulo another. It is the first deep reciprocity law: local solvability at two primes is related by a remarkably simple sign.
Legendre symbol and Euler's criterion
Definition. For an odd prime \(p\), \[ \left(\frac ap\right)= \begin{cases} 0,&p\mid a,\\ 1,&a\not\equiv0\pmod p\text{ is a square},\\ -1,&\text{otherwise}. \end{cases} \]
Theorem (Euler's criterion). \[ \left(\frac ap\right)\equiv a^{(p-1)/2}\pmod p. \]
Proof. In the cyclic group \(\mathbb F_p^\times=\langle g\rangle\), write \(a=g^k\). It is a square exactly when \(k\) is even. Since \(g^{(p-1)/2}=-1\), \[ a^{(p-1)/2}=(-1)^k, \] which gives the symbol. Multiplicativity follows immediately.
Gauss's lemma
Gauss's lemma. Let \(p\nmid a\), and let \(m\) be the number of least absolute residues of \[ a,2a,\ldots,\frac{p-1}{2}a \] that are negative. Then \[ \left(\frac ap\right)=(-1)^m. \]
Proof. The absolute values of these residues are a permutation of \(1,\ldots,(p-1)/2\). Multiplying them gives \[ a^{(p-1)/2}\left(\frac{p-1}{2}\right)! \equiv(-1)^m\left(\frac{p-1}{2}\right)!\pmod p. \] Cancel the nonzero factorial and apply Euler's criterion.
Quadratic reciprocity
Theorem (quadratic reciprocity). For distinct odd primes \(p,q\), \[ \left(\frac pq\right)\left(\frac qp\right) =(-1)^{(p-1)(q-1)/4}. \] Moreover, \[ \left(\frac{-1}{p}\right)=(-1)^{(p-1)/2},\qquad \left(\frac2p\right)=(-1)^{(p^2-1)/8}. \]
Proof. Gauss's lemma identifies \((q/p)\) with \((-1)^N\), where \(N\) counts lattice points \((i,j)\) satisfying \[ 1\le i\le\frac{p-1}{2},\quad 1\le j\le\frac{q-1}{2},\quad qi>pj. \] The complementary count gives \((p/q)=(-1)^{N'}\). No lattice point lies on \(qi=pj\), and \[ N+N'=\frac{p-1}{2}\frac{q-1}{2}, \] proving reciprocity. The supplementary laws follow directly from Gauss's lemma by counting negative residues.
Example. To decide whether \(29\) is a square modulo \(53\), reciprocity gives \[ \left(\frac{29}{53}\right) =\left(\frac{53}{29}\right) =\left(\frac{-5}{29}\right) =\left(\frac{-1}{29}\right) \left(\frac5{29}\right) =\left(\frac{29}{5}\right) =\left(\frac45\right)=1. \] Thus \(x^2\equiv29\pmod{53}\) has two solutions.