The law of quadratic reciprocity

Theorem

The law of quadratic reciprocity

T-078Home MU-207Threads number

Statement

Let \(p\) and \(q\) be distinct odd primes, and for an integer \(a\) coprime to a prime \(\ell\) let \(\left(\frac{a}{\ell}\right)\) denote the Legendre symbol, equal to \(+1\) if \(a\) is a nonzero square modulo \(\ell\) and \(-1\) otherwise. Then \[ \left(\frac{p}{q}\right)\left(\frac{q}{p}\right) = (-1)^{\frac{p-1}{2}\cdot\frac{q-1}{2}}. \] Equivalently: if at least one of \(p,q\) is congruent to \(1 \pmod 4\), then \(p\) is a square mod \(q\) if and only if \(q\) is a square mod \(p\); if both \(p\) and \(q\) are congruent to \(3 \pmod 4\), then \(p\) is a square mod \(q\) if and only if \(q\) is a non-square mod \(p\).

Why it matters

On its face, solvability of \(x^2 \equiv p \pmod q\) and solvability of \(x^2 \equiv q \pmod p\) look like unrelated questions about two different moduli. Quadratic reciprocity says they are the same question, up to a sign controlled by nothing more than the residues of \(p,q\) modulo \(4\). Gauss called it the \emph{theorema aureum} (golden theorem) and gave eight proofs across his life; it was the first deep phenomenon in the arithmetic of \(\mathbb{Z}\) that could not be seen by elementary manipulation alone, and it opened the door to the whole theory of reciprocity laws in higher-degree fields, culminating in class field theory and the Langlands programme.

Practically, together with the supplementary laws for \(\left(\frac{-1}{p}\right)\) and \(\left(\frac{2}{p}\right)\) it gives an algorithm — essentially the Euclidean algorithm run on Legendre/Jacobi symbols — for deciding whether \(a\) is a square mod \(p\) in time polynomial in \(\log p\), without ever computing \(a^{(p-1)/2}\) by fast exponentiation, and it underlies primality tests (Solovay–Strassen) and the structure theory of quadratic fields \(\mathbb{Q}(\sqrt{d})\).

Hypotheses

\(p\) and \(q\) are primes.For composite moduli the Legendre symbol is not even defined by "square or not" in the same clean way; one must pass to the Jacobi symbol, which is multiplicative but for which \(\left(\frac{a}{n}\right)=1\) no longer implies \(a\) is a square mod \(n\) (e.g. \(\left(\frac{2}{9}\right)=1\) yet \(2\) is not a square mod \(9\)). The reciprocity law itself still holds for the Jacobi symbol, but its interpretation as "is a square" breaks. \(p\) and \(q\) are odd.The symbol \(\left(\frac{2}{p}\right)\) obeys a different, "supplementary" law, \(\left(\frac{2}{p}\right)=(-1)^{(p^2-1)/8}\), not the reciprocity formula above; \(2\) plays a structurally different role because the group \((\mathbb{Z}/2^k\mathbb{Z})^\times\) is not cyclic for \(k\ge3\). \(p \neq q\).If \(p=q\) the symbol \(\left(\frac{p}{p}\right)\) is conventionally \(0\) (or undefined, since \(p \mid p\)), so the statement is vacuous/ill-posed; the whole argument below relies on \(p,q\) being coprime so that neither symbol has a zero factor.

The lattice-point count needs no point of the rectangle to lie exactly on the diagonal \(qx=py\).This is not an extra hypothesis to be assumed — it is a consequence of \(p\neq q\) both prime (if \(qx=py\) with \(1\le x\le\frac{p-1}{2}\) then \(p\mid qx\), and since \(p\nmid q\), \(p\mid x\), impossible as \(x\lt p\)) — but it is worth flagging because the entire counting argument in Step 5 of the proof silently depends on it, and dropping \(p\ne q\) or primality of both moduli destroys it.

Proof

\left(\frac{a}{\ell}\right) \equiv a^{\frac{\ell-1}{2}} \pmod \ell \quad \text{(Euler's Criterion)}

Cited lemma. \((\mathbb{Z}/\ell\mathbb{Z})^\times\) is cyclic of order \(\ell-1\) (standard fact for finite fields); the squares form the unique index-\(2\) subgroup, which is exactly the kernel of the homomorphism \(a\mapsto a^{(\ell-1)/2}\) into \(\{\pm1\}\), since that homomorphism is surjective (a generator does not map to \(1\)) with kernel of index \(2\). This is used only to fix sign conventions; the proof itself proceeds via Gauss's Lemma. A

\text{(Gauss's Lemma) For } \gcd(a,\ell)=1,\ \ell \text{ an odd prime: } \left(\frac{a}{\ell}\right) = (-1)^{\mu}, \quad \mu = \#\Big\{\,k \in \big[1,\tfrac{\ell-1}{2}\big] : \big(ak \bmod \ell\big) \gt \tfrac{\ell}{2} \,\Big\}.

Proof of the lemma: for \(k=1,\dots,\frac{\ell-1}{2}\) let \(r_k\) be the least positive residue of \(ak\) mod \(\ell\) (all distinct and nonzero as \(\gcd(a,\ell)=1\)), and set \(r_k' = r_k\) if \(r_k\lt\ell/2\), else \(r_k'=r_k-\ell\) (so \(r_k'\lt0\)). The absolute values \(|r_1'|,\dots,|r_{(\ell-1)/2}'|\) are a permutation of \(1,\dots,\frac{\ell-1}{2}\): they are distinct (if \(|r_i'|=|r_j'|\) then \(ai\equiv \pm aj\), forcing \(i\equiv\pm j\), so \(i=j\) since both lie in \([1,\frac{\ell-1}{2}]\)) and there are exactly \(\frac{\ell-1}{2}\) of them in that range. Multiplying, \(a^{\frac{\ell-1}{2}}\prod k \equiv \prod r_k = (-1)^{\mu}\prod|r_k'| = (-1)^{\mu}\prod k \pmod \ell\); cancelling \(\prod k\) (coprime to \(\ell\)) gives \(a^{(\ell-1)/2}\equiv(-1)^{\mu}\), and Euler's Criterion (Step 1) identifies the left side with \(\left(\frac{a}{\ell}\right)\). C

\text{(Eisenstein's Lemma) For odd } a \text{ with } \gcd(a,\ell)=1: \quad \left(\frac{a}{\ell}\right) = (-1)^{F},\qquad F=\sum_{k=1}^{(\ell-1)/2}\left\lfloor \frac{ak}{\ell}\right\rfloor.

Write \(ak=\ell\lfloor ak/\ell\rfloor + r_k\) with \(r_k\) as in Step 2, and sum over \(k=1,\dots,\frac{\ell-1}{2}\); with \(T=\sum k = \tfrac{1}{8}(\ell-1)(\ell+1)/... \) — the exact value of \(T\) is irrelevant, only its role below. We get \(aT = \ell F + \sum r_k\). Using \(r_k = r_k' + \ell\) when \(r_k\gt\ell/2\) (else \(r_k=r_k'\)), \(\sum r_k = \sum r_k' + \mu\ell\). Since \(r_k' \equiv -r_k' \equiv |r_k'| \pmod 2\) always (as \(2r_k'\equiv0\)), and \(\{|r_k'|\}=\{1,\dots,\tfrac{\ell-1}{2}\}\) from Step 2, \(\sum r_k' \equiv T \pmod 2\). Hence \(\sum r_k \equiv T+\mu\ell \pmod2\), and \(aT \equiv \ell F + T + \mu\ell \pmod 2\). Because \(a\) and \(\ell\) are both odd, \(aT\equiv T\) and \(\ell F\equiv F\), \(\mu\ell\equiv\mu \pmod2\); so \(T \equiv F+T+\mu\), giving \(\mu\equiv F \pmod 2\). Substituting into Gauss's Lemma (Step 2) proves the claim. C

S_1 := \sum_{x=1}^{(p-1)/2}\left\lfloor\frac{qx}{p}\right\rfloor, \qquad S_2 := \sum_{y=1}^{(q-1)/2}\left\lfloor\frac{py}{q}\right\rfloor.

Apply Eisenstein's Lemma (Step 3) with \(\ell=p,\,a=q\) (legitimate: \(q\) is odd, \(\gcd(q,p)=1\)) to get \(\left(\frac{q}{p}\right)=(-1)^{S_1}\); apply it with \(\ell=q,\,a=p\) to get \(\left(\frac{p}{q}\right)=(-1)^{S_2}\). A

S_1 + S_2 = \frac{p-1}{2}\cdot\frac{q-1}{2}.

Key geometric step. Consider the open rectangle of lattice points \(R=\{(x,y)\in\mathbb{Z}^2 : 1\le x\le \tfrac{p-1}{2},\ 1\le y\le\tfrac{q-1}{2}\}\), which has exactly \(\tfrac{p-1}{2}\cdot\tfrac{q-1}{2}\) points, none on the line \(qx=py\) (Hypotheses, last item, since \(p,q\) are distinct primes). Each point of \(R\) lies strictly above or strictly below that line. For fixed \(x\), the number of \(y\in[1,\tfrac{q-1}{2}]\) with \(y \lt qx/p\) is exactly \(\lfloor qx/p\rfloor\) (since \(qx/p \lt q/2\cdot(p-1)/p \lt q/2\), the floor already lies in range), so summing over \(x\) counts the points below the line: this total is \(S_1\). Symmetrically, for fixed \(y\), the number of \(x\in[1,\tfrac{p-1}{2}]\) with \(x \lt py/q\) is \(\lfloor py/q\rfloor\), so summing over \(y\) counts the points \(above\) the line (those with \(x\lt py/q \iff qx\lt py \iff y \gt qx/p\)): this total is \(S_2\). Since every point of \(R\) is above or below the line, \(S_1+S_2=|R|\). B

\left(\frac{p}{q}\right)\left(\frac{q}{p}\right) = (-1)^{S_2}(-1)^{S_1} = (-1)^{S_1+S_2} = (-1)^{\frac{p-1}{2}\cdot\frac{q-1}{2}}.

Multiply the two identities of Step 4 and substitute Step 5. This is exactly the claimed statement. A

Result

\left(\frac{p}{q}\right)\left(\frac{q}{p}\right) = (-1)^{\frac{p-1}{2}\cdot\frac{q-1}{2}}, \qquad p,q \text{ distinct odd primes}

Reading. Two distinct odd primes "reciprocate": whether \(p\) is a quadratic residue mod \(q\) matches whether \(q\) is a quadratic residue mod \(p\), except when both \(p\equiv q\equiv 3\pmod4\), in which case the two answers are opposite. The sign \((-1)^{\frac{p-1}{2}\cdot\frac{q-1}{2}}\) is \(-1\) exactly when both \(\frac{p-1}{2}\) and \(\frac{q-1}{2}\) are odd, i.e. exactly when \(p\equiv q\equiv3\pmod4\).

Scope. Applies to any pair of distinct odd primes \(p,q\), with no further restriction. Combined with the two supplementary laws \(\left(\frac{-1}{p}\right)=(-1)^{(p-1)/2}\) and \(\left(\frac{2}{p}\right)=(-1)^{(p^2-1)/8}\), and with the multiplicativity \(\left(\frac{ab}{p}\right)=\left(\frac{a}{p}\right)\left(\frac{b}{p}\right)\), it determines \(\left(\frac{a}{p}\right)\) for every \(a\) coprime to \(p\) via factorisation of \(a\) and repeated symbol-flipping (or, more efficiently, via the Jacobi symbol, which needs no factorisation).

Corollaries & converses

If \(p\equiv1\pmod4\) then \(\left(\frac{p}{q}\right)=\left(\frac{q}{p}\right)\) for every odd prime \(q\neq p\) — the sign is unconditionally \(+1\) regardless of \(q\), since \(\frac{p-1}{2}\) is even.
If \(p\equiv q\equiv3\pmod4\) then \(\left(\frac{p}{q}\right)=-\left(\frac{q}{p}\right)\); this is the only case where the two symbols differ.
Combined with the two supplementary laws, reciprocity gives an \(O((\log p)(\log q))\)-time algorithm for computing \(\left(\frac{a}{p}\right)\) via the Jacobi-symbol version of Euclid's algorithm (repeatedly reduce and flip), avoiding both factorisation and modular exponentiation.
The theorem extends verbatim (with the same proof shape) to the Jacobi symbol \(\left(\frac{m}{n}\right)\) for odd coprime \(m,n\gt0\), not just primes — this is the version actually used in fast computation.
Converse. The statement is an "if and only if" biconditional already (it pins down the product of the two symbols exactly, not just an implication), so there is no separate converse to check; the identity determines \(\left(\frac{p}{q}\right)\) from \(\left(\frac{q}{p}\right)\) and vice versa in every case, since both symbols are \(\pm1\).

Fails without

Dropping "\(p,q\) prime" (Jacobi symbols with composite arguments, misread as "square or not"): take \(n=9\), \(a=2\). The Jacobi symbol \(\left(\frac{2}{9}\right)=\left(\frac{2}{3}\right)^2=(-1)^2=1\), yet \(2\) is not a quadratic residue mod \(9\) (squares mod \(9\) are \(0,1,4,7\)); the reciprocity-style law for Jacobi symbols is still true as an identity of symbols, but "\(\left(\frac{a}{n}\right)=1\)" no longer means "\(a\) is a square mod \(n\)" once \(n\) is composite, so applying the theorem's conclusion in its quadratic-residue reading to a composite modulus gives a false statement.
Dropping "odd" and using \(\ell=2\): the formula \(\left(\frac{p}{2}\right)\left(\frac{2}{p}\right)=(-1)^{\cdots}\) with \(\frac{2-1}{2}=\frac12\) is not even an integer, so the stated formula is not merely false but ill-formed; the correct replacement, \(\left(\frac{2}{p}\right)=(-1)^{(p^2-1)/8}\), has a genuinely different shape (depends on \(p\) mod \(8\), not mod \(4\)) and is proved by a separate (though related) lattice-point argument, not a special case of the odd–odd formula.
Ignoring \(p\neq q\): the "proof" of Step 5 collapses since the diagonal \(qx=py\) becomes \(x=y\), which does pass through lattice points of the rectangle, so \(S_1+S_2\) undercounts \(|R|\) by the number of diagonal points; concretely \(\left(\frac{p}{p}\right)\) is not \(\pm1\) at all (it is \(0\) by convention, since \(p\mid p\)), so the product on the left of the theorem is \(0\), not \(\pm1\) as the right-hand side would require.

Common errors

Misremembering the exponent as \(\frac{(p-1)(q-1)}{2}\) instead of \(\frac{p-1}{2}\cdot\frac{q-1}{2}\) — these are generally different integers, not just different-looking expressions for the same parity: e.g. \(p=3,q=7\) gives \(\frac{p-1}{2}\cdot\frac{q-1}{2}=1\cdot3=3\) (odd, sign \(-1\)) but \(\frac{(p-1)(q-1)}{2}=\frac{2\cdot6}{2}=6\) (even, sign \(+1\)) — the mis-simplified version gives the wrong sign here. The safe habit is to always compute \(\frac{p-1}{2}\) and \(\frac{q-1}{2}\) separately as integers first, then multiply.
Applying the odd–odd formula directly to \(\left(\frac{2}{p}\right)\) or \(\left(\frac{-1}{p}\right)\); these need their own supplementary laws, not the reciprocity formula, since \(2\) is not an odd prime and \(-1\) is not a prime at all.
Forgetting that \(\left(\frac{a}{p}\right)\) is only defined (as \(\pm1\)) when \(p\nmid a\); plugging in \(a\) with \(p\mid a\) and treating the "value" as \(1\) rather than \(0\) silently corrupts later multiplicativity arguments.
Assuming the Jacobi symbol \(\left(\frac{a}{n}\right)=1\) for composite odd \(n\) certifies that \(a\) is a quadratic residue mod \(n\) — false in general (see Fails without); the Jacobi symbol is a useful computational proxy, not a residue test, unless \(n\) is prime.
Sign errors when converting between "\(\left(\frac{p}{q}\right)=\left(\frac{q}{p}\right)\)" and "\(\left(\frac{p}{q}\right)=-\left(\frac{q}{p}\right)\)" — students often test only one of \(p,q\) mod \(4\) instead of checking that \emph{both} are \(\equiv3\pmod4\) before flipping the sign.

Discussion

Gauss first proved quadratic reciprocity in 1796 (published in the \emph{Disquisitiones Arithmeticae}, 1801), calling it the golden theorem, and returned to it repeatedly, eventually publishing eight distinct proofs; he sought generalisations to cubic and biquadratic reciprocity, which forced him to work in the Gaussian integers \(\mathbb{Z}[i]\) and foreshadowed algebraic number theory. Eisenstein's lattice-point proof given above, from 1844, is among the shortest classical proofs and is the one most commonly taught, but it is worth knowing it is one of many genuinely different arguments — others use Gauss sums (a proof via roots of unity and the quadratic Gauss sum \(g=\sum_{a}\left(\frac{a}{p}\right)\zeta_p^a\), showing \(g^2=(-1)^{(p-1)/2}p\) and working in \(\mathbb{Z}[\zeta_p]\)), and yet others are genuinely algebraic, via Frobenius elements in cyclotomic fields.

The theorem is the prototype for a vast family of "reciprocity laws" in number theory. Cubic and biquadratic reciprocity (Eisenstein, Gauss) govern \(x^3\equiv a\) and \(x^4\equiv a\) but require working over \(\mathbb{Z}[\omega]\) and \(\mathbb{Z}[i]\) respectively rather than \(\mathbb{Z}\), because the relevant unit groups and ramification behave differently. The Artin reciprocity law of class field theory (1920s) recasts quadratic (and all abelian) reciprocity as a statement about Galois groups of abelian extensions of number fields being described by data purely local at each prime; quadratic reciprocity is the abelian extension \(\mathbb{Q}(\sqrt{p^*})/\mathbb{Q}\) case. The Langlands programme conjecturally extends this to non-abelian settings.

A cleaner conceptual proof, closer to the modern viewpoint, computes the quadratic Gauss sum \(g_p=\sum_{a=0}^{p-1}\left(\frac{a}{p}\right)e^{2\pi i a/p}\), shows \(g_p^2=(-1)^{(p-1)/2}p\) by an elementary character-sum manipulation, then reduces \(g_p^{q-1} \pmod q\) two different ways inside the ring \(\mathbb{Z}[\zeta_p]/(q)\) — once using the Frobenius endomorphism \(x\mapsto x^q\) in characteristic \(q\), once using Euler's criterion directly — and equates the results. This proof generalises far more readily (to higher reciprocity laws) than Eisenstein's, at the cost of needing algebraic number theory machinery that would be circular to invoke inside an elementary Phase 2 course.

Common misconception: that reciprocity tells you the value of \(\left(\frac{p}{q}\right)\) outright. It does not — it only relates \(\left(\frac{p}{q}\right)\) to \(\left(\frac{q}{p}\right)\); computing an actual value still requires reducing \(p\) mod \(q\) (or vice versa) and recursing, typically via the Euclidean-algorithm-style descent using the Jacobi symbol.

Worked examples

\text{Determine whether } 71 \text{ is a quadratic residue mod } 97 \text{ (both prime).}

Both \(71,97\) are odd primes, \(97\) prime confirmed, \(71\) prime confirmed; reciprocity applies directly. A

71 \equiv 3 \pmod4, \qquad 97\equiv1\pmod4.

Direct computation of residues mod \(4\). A

\text{Since } 97\equiv1\pmod4,\ \tfrac{97-1}{2}=48 \text{ is even, so } \left(\frac{71}{97}\right)\left(\frac{97}{71}\right)=(-1)^{48\cdot35}=1.

Apply the Theorem (Result box): the exponent \(\tfrac{p-1}{2}\cdot\tfrac{q-1}{2}\) with \(p=71,q=97\) has an even factor \(\tfrac{97-1}{2}=48\), so the product is \(+1\). B

\left(\frac{97}{71}\right) = \left(\frac{97-71}{71}\right) = \left(\frac{26}{71}\right) = \left(\frac{2}{71}\right)\left(\frac{13}{71}\right).

Reduce \(97\) mod \(71\) (Legendre symbol depends only on the residue class, since \(a\equiv b\pmod\ell \Rightarrow \left(\frac{a}{\ell}\right)=\left(\frac{b}{\ell}\right)\)), then split \(26=2\cdot13\) via multiplicativity of the Legendre symbol. A

\left(\frac{2}{71}\right) = (-1)^{(71^2-1)/8} = (-1)^{630} = 1, \qquad 71\equiv7\pmod8.

Supplementary law for \(2\) (cited, proved by a companion lattice-point argument to Step 3 of the main proof, not reproduced here); \(71^2-1=5040\), \(5040/8=630\), even. B

\left(\frac{13}{71}\right)\left(\frac{71}{13}\right) = (-1)^{6\cdot35}=1 \ \Rightarrow\ \left(\frac{13}{71}\right)=\left(\frac{71}{13}\right)=\left(\frac{6}{13}\right)=\left(\frac{2}{13}\right)\left(\frac{3}{13}\right).

Apply reciprocity again to the smaller pair \((13,71)\) (both odd primes, \(\tfrac{13-1}{2}=6\) even so product is \(+1\)); reduce \(71\equiv6\pmod{13}\); split \(6=2\cdot3\). B

\left(\frac{2}{13}\right)=(-1)^{(169-1)/8}=(-1)^{21}=-1, \qquad \left(\frac{3}{13}\right)\left(\frac{13}{3}\right)=(-1)^{1\cdot6}=1 \Rightarrow \left(\frac{3}{13}\right)=\left(\frac{13}{3}\right)=\left(\frac{1}{3}\right)=1.

Supplementary law for \(\left(\frac{2}{13}\right)\); reciprocity for \((3,13)\) with \(\tfrac{3-1}{2}=1\) odd, \(\tfrac{13-1}{2}=6\) even, exponent even so sign \(+1\); reduce \(13\equiv1\pmod3\), and \(1\) is trivially a square. A

\left(\frac{13}{71}\right)=(-1)(1)=-1 \ \Rightarrow\ \left(\frac{97}{71}\right)=1\cdot(-1)=-1 \ \Rightarrow\ \left(\frac{71}{97}\right)=\left(\frac{97}{71}\right)=-1

Reading. \(71\) is not a quadratic residue mod \(97\): there is no integer \(x\) with \(x^2\equiv71\pmod{97}\). The final equality used Step 3 (sign \(+1\)) to pass from \(\left(\frac{97}{71}\right)\) back to \(\left(\frac{71}{97}\right)\).

\text{Determine whether } x^2\equiv-1\pmod{p} \text{ is solvable for } p=79 \text{ and relate it to a reciprocity computation.}

Setup: this is asking for \(\left(\frac{-1}{79}\right)\), which needs the supplementary law, not reciprocity directly — included to show how reciprocity interacts with it in a factorisation. A

\left(\frac{-1}{79}\right) = (-1)^{(79-1)/2} = (-1)^{39} = -1.

Supplementary law \(\left(\frac{-1}{p}\right)=(-1)^{(p-1)/2}\) (an immediate corollary of Euler's Criterion, Step 1 of the main proof, since \((-1)^{(p-1)/2}\equiv(-1)^{(p-1)/2}\) trivially — more precisely it is Euler's Criterion applied to \(a=-1\) directly, no reciprocity needed). Since \(79=4\cdot19+3\), \(\tfrac{79-1}{2}=39\) is odd. A

\text{Now compute } \left(\frac{5}{79}\right) \text{ using reciprocity, to combine with the above via } \left(\frac{-5}{79}\right)=\left(\frac{-1}{79}\right)\left(\frac{5}{79}\right).

Multiplicativity of the Legendre symbol splits \(-5=(-1)\cdot5\). A

\left(\frac{5}{79}\right)\left(\frac{79}{5}\right) = (-1)^{\frac{5-1}{2}\cdot\frac{79-1}{2}} = (-1)^{2\cdot39} = 1 \ \Rightarrow\ \left(\frac{5}{79}\right)=\left(\frac{79}{5}\right).

Apply the Theorem to \(p=5,q=79\); \(\tfrac{5-1}{2}=2\) is even, so the product is \(+1\) regardless of \(\tfrac{79-1}{2}\), giving equality of the two symbols directly (this is the "\(p\equiv1\pmod4\)" corollary — note \(5\equiv1\pmod4\)). B

\left(\frac{79}{5}\right) = \left(\frac{79 \bmod 5}{5}\right) = \left(\frac{4}{5}\right) = \left(\frac{2^2}{5}\right) = 1.

Reduce \(79\equiv4\pmod5\); \(4\) is a perfect square, so trivially a quadratic residue mod any prime not dividing it. A

\left(\frac{5}{79}\right)=1, \qquad \left(\frac{-5}{79}\right)=\left(\frac{-1}{79}\right)\left(\frac{5}{79}\right)=(-1)(1)=-1

Reading. \(x^2\equiv5\pmod{79}\) is solvable, but \(x^2\equiv-1\pmod{79}\) and \(x^2\equiv-5\pmod{79}\) are not. This illustrates reciprocity being used as one ingredient (for the prime factor \(5\)) inside a larger multiplicative computation alongside the supplementary law for \(-1\).

Problems

Compute \(\left(\frac{29}{53}\right)\) using quadratic reciprocity (both \(29\) and \(53\) are prime).
Solution
\(29\equiv1\pmod4\) (since \(\tfrac{29-1}{2}=14\) is even), so by the corollary in the Result box, \(\left(\frac{29}{53}\right)=\left(\frac{53}{29}\right)\). Reduce: \(53\equiv24\pmod{29}\), so \(\left(\frac{53}{29}\right)=\left(\frac{24}{29}\right)=\left(\frac{4}{29}\right)\left(\frac{6}{29}\right)=\left(\frac{6}{29}\right)\) (as \(4\) is a square) \(=\left(\frac{2}{29}\right)\left(\frac{3}{29}\right)\). Supplementary law: \(29\equiv5\pmod8\), so \(\left(\frac{2}{29}\right)=(-1)^{(29^2-1)/8}=(-1)^{105}=-1\). For \(\left(\frac{3}{29}\right)\): \(\tfrac{3-1}{2}=1\) odd, \(\tfrac{29-1}{2}=14\) even, product even, so \(\left(\frac{3}{29}\right)=\left(\frac{29}{3}\right)=\left(\frac{2}{3}\right)\). Direct check mod \(3\): squares mod \(3\) are \(\{0,1\}\), so \(2\) is not a square, \(\left(\frac{2}{3}\right)=-1\). Hence \(\left(\frac{3}{29}\right)=-1\), and \(\left(\frac{29}{53}\right)=(-1)(-1)=1\).
Without reciprocity, using only the direct definition, explain why \(\left(\frac{p}{p}\right)\) must be excluded from the theorem's hypotheses, and state its conventional value.
Solution
The Legendre symbol \(\left(\frac{a}{\ell}\right)\) is defined for \(a\) coprime to \(\ell\); when \(a=\ell\), \(\ell \mid a\), so \(a\) is neither a nonzero square nor a non-square mod \(\ell\) — it is the zero residue. By convention \(\left(\frac{\ell}{\ell}\right)=0\). Since the theorem's right-hand side \((-1)^{(p-1)/2\cdot(q-1)/2}\) is always \(\pm1\), never \(0\), the identity would fail outright if \(p=q\) were permitted (the left side would be \(0\), the right side \(\pm1\)); this is exactly why \(p\neq q\) is a hypothesis, not a convenience.
Use the supplementary law together with reciprocity to determine all primes \(p\) for which \(-2\) is a quadratic residue mod \(p\) (\(p\) odd, \(p\neq2\)), expressing the answer as a condition on \(p\) mod \(8\).
Solution
\(\left(\frac{-2}{p}\right)=\left(\frac{-1}{p}\right)\left(\frac{2}{p}\right)=(-1)^{(p-1)/2}\cdot(-1)^{(p^2-1)/8}\). Write \(p\bmod8\in\{1,3,5,7\}\) (odd). For \(p\equiv1\pmod8\): \((p-1)/2\) even, \((p^2-1)/8\) even, product \(+1\cdot+1=1\). For \(p\equiv3\pmod8\): \((p-1)/2\) odd (since \(p=8k+3\Rightarrow(p-1)/2=4k+1\)), \((p^2-1)/8=(8k+3)^2-1)/8 = (64k^2+48k+8)/8=8k^2+6k+1\), odd; product \((-1)(-1)=1\). For \(p\equiv5\pmod8\): \((p-1)/2=4k+2\) even (\(p=8k+5\)); \((p^2-1)/8=(64k^2+80k+24)/8=8k^2+10k+3\), odd; product \((+1)(-1)=-1\). For \(p\equiv7\pmod8\): \((p-1)/2=4k+3\) odd (\(p=8k+7\)); \((p^2-1)/8=(64k^2+112k+48)/8=8k^2+14k+6\), even; product \((-1)(+1)=-1\). So \(-2\) is a quadratic residue mod \(p\) exactly when \(p\equiv1\) or \(3\pmod8\), reproducing the classical result for the field \(\mathbb{Q}(\sqrt{-2})\).
A student claims: "since \(\left(\frac{a}{p}\right)^2=1\) for all \(a\) coprime to \(p\), reciprocity is trivial because both sides of the identity are automatically \(1\)." Explain the error.
Solution
The student has confused \(\left(\frac{a}{p}\right)^2=1\) (true, since \(\left(\frac{a}{p}\right)\in\{\pm1\}\) always squares to \(1\)) with the actual claim of the theorem, which is about the product \(\left(\frac{p}{q}\right)\left(\frac{q}{p}\right)\) of \emph{two different} symbols — one with \(p\) as the "top", one with \(q\) as the "top" — not the square of a single symbol. This product is \(+1\) or \(-1\) depending on \(p,q\) mod \(4\), and is genuinely non-trivial information (e.g. Worked Example 1 shows a case where the two individual symbols are both \(-1\), and Worked Example 2 combines a case where they are forced equal). The theorem would be trivial only if it asserted \(\left(\frac{p}{q}\right)^2=1\), which is a different and much weaker statement.
Prove, as a corollary of quadratic reciprocity and the supplementary laws (do not assume it independently), that if \(p\equiv1\pmod4\) is prime, then \(p\) can be written in a form related to sums of two squares by showing \(-1\) is a quadratic residue mod \(p\); then state (without reproving) how this feeds into Fermat's two-square theorem.
Solution
By the supplementary law (Step 1 of the main proof, Euler's Criterion, applied to \(a=-1\)): \(\left(\frac{-1}{p}\right)=(-1)^{(p-1)/2}\). If \(p\equiv1\pmod4\), write \(p=4k+1\), so \((p-1)/2=2k\) is even, giving \(\left(\frac{-1}{p}\right)=1\): \(-1\) is a quadratic residue mod \(p\), i.e. there exists \(x\) with \(x^2\equiv-1\pmod p\), so \(p \mid x^2+1\). This is precisely the number-theoretic fact used as the starting point of Fermat's two-square theorem: since \(p\mid x^2+1^2\) but \(p\) does not divide \(x\pm i\) in \(\mathbb{Z}[i]\) individually (as \(p\) is not a Gaussian integer multiple of either factor, else it would divide their difference \(2i\) or sum), \(p\) is not a Gaussian prime, hence factors as \(p=\pi\bar\pi\) in \(\mathbb{Z}[i]\), which unwinds to \(p=a^2+b^2\) for integers \(a,b\) — the full proof of that unwinding is a separate theorem (Fermat's two-square theorem) and is not reproved here; only the reciprocity-supplied input \(\left(\frac{-1}{p}\right)=1\) is being derived and cited.