21.01.07 · number-theory / elementary

Quadratic reciprocity (Gauss's theorema aureum)

shipped3 tiersLean: none

Anchor (Master): Gauss 1801 *Disquisitiones Arithmeticae* arts. 125-152 (originator: the first complete proof of quadratic reciprocity by induction, called the theorema aureum); Gauss 1808 *Theorematis arithmetici demonstratio nova* (Göttingen) (Gauss's third proof via the lemma and absolute-residue counting); Gauss 1818 *Theorematis fundamentalis in doctrina de residuis quadraticis demonstrationes et amplificationes novae* (Werke II, 47-64) (Gauss's fourth, fifth, sixth proofs — including the Gauss-sum proof); Eisenstein 1845 *J. reine angew. Math.* 28, 246-248 (Eisenstein's geometric lattice-point counting proof — the canonical modern textbook proof); Eisenstein 1844 *J. reine angew. Math.* 27, 289-310 (cubic and biquadratic reciprocity in $\mathbb{Z}[\zeta_3]$ and $\mathbb{Z}[i]$); Dirichlet 1854 (Gauss-sum proof using cyclotomic fields, expanded in Dedekind's edition of Dirichlet's *Vorlesungen* 1894); Hilbert 1897 *Jahresber. DMV* 4, 175-546 (Hilbert symbol and the product formula $\prod_v (a, b)_v = 1$); Hilbert 1900 ICM Paris (the 9th problem on general reciprocity); Takagi 1920 *J. Coll. Sci. Tokyo* 41, 1-133 (class field theory for abelian extensions of number fields); Artin 1927 *Hamb. Abh.* 5, 353-363 (Artin reciprocity, the modern formulation); Furtwängler 1909 *Math. Ann.* 67, 1-31 (Eisenstein reciprocity for the $\ell$-th power residue symbol); Lemmermeyer 2000 *Reciprocity Laws: From Euler to Eisenstein* (Springer Monographs in Mathematics) (catalogue of 300+ independent proofs); Ireland-Rosen 1990 *A Classical Introduction to Modern Number Theory* §§5-6; Serre 1973 *A Course in Arithmetic* (Springer GTM 7) Ch. I §3

Intuition Beginner

The law of quadratic reciprocity is a single equation that connects two completely separate-looking questions. Pick two distinct odd primes $p$ and $q$ . The first question: is $p$ a square modulo $q$ ? The second question: is $q$ a square modulo $p$ ? On the face of it these questions have nothing to do with each other — one is arithmetic inside the field $Z / q$ , the other is arithmetic inside the field $Z / p$ . Gauss discovered in 1796 that the answers are linked by a clean rule depending only on the residues of $p$ and $q$ modulo $4$ .

The rule. If at least one of $p, q$ is congruent to $1$ modulo $4$ , then $p$ is a square modulo $q$ if and only if $q$ is a square modulo $p$ . If both $p$ and $q$ are congruent to $3$ modulo $4$ , then $p$ is a square modulo $q$ if and only if $q$ is not a square modulo $p$ . So the two answers agree when the primes are well-behaved at the residue $1 (mod 4)$ , and they flip when both primes are stubborn at the residue $3 (mod 4)$ .

Worked example. Is $3$ a square modulo $7$ ? We have $p = 3, q = 7$ , both $\equiv 3 (mod 4)$ , so the answers flip. Is $7$ a square modulo $3$ ? Reduce $7 \equiv 1 (mod 3)$ , and $1 = 1^{2}$ is a square. So $7$ is a square modulo $3$ . By the flip, $3$ is not a square modulo $7$ . Cross-check by listing the squares modulo $7$ : the squares of $1, 2, 3$ are $1, 4, 2$ , so the squares modulo $7$ are ${1, 2, 4}$ , and $3$ is not on the list. The reciprocity rule got the right answer.

The compact form. Use the Legendre symbol $(a / p)$ from the previous unit. The law of quadratic reciprocity says, for distinct odd primes $p, q$ , $$ \left(\frac{p}{q}\right) \left(\frac{q}{p}\right) ;=; (-1)^{\frac{p - 1}{2} \cdot \frac{q - 1}{2}}. $$ The right-hand side is $+ 1$ unless both $p$ and $q$ are $\equiv 3 (mod 4)$ , in which case it is $- 1$ . So $(p / q) = (q / p)$ in the good case and $(p / q) = - (q / p)$ in the flip case.

Why does this matter? Two reasons. First, it converts an existence question modulo $q$ into a related question modulo $p$ , so we can flip back and forth between the two primes, reducing the larger argument each time. Combined with the multiplicative property of the Legendre symbol and the two supplementary laws for $(- 1/ p)$ and $(2/ p)$ , the reciprocity law gives a complete algorithm for computing any Legendre symbol $(a / p)$ in time roughly $lo g p$ steps — far faster than searching for square roots. Second, it is the foundational example of a reciprocity law, a kind of relation that underlies all modern number theory: cubic reciprocity, biquadratic reciprocity, Artin reciprocity, and the Langlands programme all descend from this single elementary observation.

Gauss called the law the theorema aureum — the golden theorem — and produced eight independent proofs of it over his lifetime. By 2026 more than three hundred independent proofs are known, catalogued in Lemmermeyer's Reciprocity Laws. The multiplicity of proofs is itself a signal: the law sits at a deep junction of arithmetic, geometry, and analysis, and each new viewpoint produces a new proof.

Visual Beginner

The reciprocity exponent $((p - 1) /2) ((q - 1) /2)$ has a clean geometric reading. It is the number of integer points inside a rectangle with sides $(p - 1) /2$ and $(q - 1) /2$ . The picture shows the rectangle for $p = 7$ and $q = 11$ .

The picture captures Eisenstein's geometric proof of the reciprocity law: the rectangle has $((p - 1) /2) ((q - 1) /2)$ interior lattice points, the diagonal of slope $q / p$ passes through no lattice point (since $g cd (p, q) = 1$ ), and the count of lattice points in the lower triangle controls $(q / p)$ via Gauss's lemma while the count in the upper triangle controls $(p / q)$ . Adding the two counts modulo $2$ recovers the reciprocity exponent.

Worked example Beginner

Compute the Legendre symbol $(29/53)$ using the law of quadratic reciprocity.

Step 1. Both $29$ and $53$ are odd primes. Reduce modulo $4$ : $29 = 4 \cdot 7 + 1 \equiv 1 (mod 4)$ , and $53 = 4 \cdot 13 + 1 \equiv 1 (mod 4)$ . Since at least one (in fact both) of the primes is $\equiv 1 (mod 4)$ , the reciprocity flip exponent $((29 - 1) /2) ((53 - 1) /2) = 14 \cdot 26 = 364$ is even, so $(29/53) = (53/29)$ .

Step 2. Reduce the larger argument $53$ modulo the smaller prime $29$ : $53 = 29 + 24$ , so $53 \equiv 24 (mod 29)$ . This gives $(53/29) = (24/29)$ .

Step 3. Factor $24 = 2^{3} \cdot 3$ and apply multiplicativity: $(24/29) = (2/29)^{3} (3/29) = (2/29) \cdot (3/29)$ , using that $(2/29)^{2} = 1$ on the cube.

Step 4. Compute $(2/29)$ via the second supplementary law $(2/ p) = (- 1)^{(p^{2} - 1) /8}$ . Here $(2 9^{2} - 1) /8 = (841 - 1) /8 = 840/8 = 105$ , odd, so $(2/29) = - 1$ . Alternatively use $29 \equiv 5 (mod 8)$ , and the supplementary law gives $(2/ p) = - 1$ for $p \equiv \pm 3 (mod 8)$ .

Step 5. Compute $(3/29)$ using reciprocity again. Both $3$ and $29$ are odd primes; $29 \equiv 1 (mod 4)$ , so the flip exponent is even and $(3/29) = (29/3)$ . Reduce $29 \equiv 2 (mod 3)$ , so $(29/3) = (2/3)$ . Apply the second supplementary law: $3 \equiv 3 (mod 8)$ , so $(2/3) = - 1$ .

Step 6. Combine: $(24/29) = (2/29) (3/29) = (- 1) (- 1) = + 1$ . Therefore $(29/53) = + 1$ , and $29$ is a quadratic residue modulo $53$ .

Cross-check by enumeration is feasible because $53$ is small. The squares modulo $53$ are the squares of $1, 2, \dots, 26$ , reducing modulo $53$ . A direct search finds $2 0^{2} = 400 = 7 \cdot 53 + 29$ , so $2 0^{2} \equiv 29 (mod 53)$ , confirming that $29$ is a square modulo $53$ .

The reciprocity computation extends to much larger primes where direct enumeration would be infeasible. The whole computation took six steps, none harder than a small modular reduction. The general algorithm uses reciprocity to halve the larger argument at each step, much like the Euclidean algorithm — and the total number of reduction steps for computing $(a / p)$ is $O (lo g p)$ .

Check your understanding Beginner

Exercise (easy, true-false).

True or false: the law of quadratic reciprocity applies to all pairs of distinct positive primes, including $p = 2$ .

Hint

Recall that the Legendre symbol $(a / p)$ is defined for $p$ an odd prime. The formula $(p / q) (q / p) = (- 1)^{((p - 1) /2) ((q - 1) /2)}$ requires the exponents $(p - 1) /2$ and $(q - 1) /2$ to be integers.

Answer

False. Quadratic reciprocity is stated for distinct odd primes $p, q$ . The Legendre symbol is undefined for $p = 2$ (the exponent $(2 - 1) /2 = 1/2$ is not an integer), and the role of the prime $2$ is played by the second supplementary law $(2/ p) = (- 1)^{(p^{2} - 1) /8}$ for $p$ an odd prime, which records the quadratic-residue status of $2$ modulo $p$ . The Kronecker-symbol extension $(a / n)$ to even moduli handles $p = 2$ adelically, but this is not the form of quadratic reciprocity itself.

Formal definition Intermediate+

We restate the reciprocity-law setup precisely, building on the Legendre-symbol framework from 21.01.06.

Definition (reciprocity exponent). For distinct odd primes $p, q$ , the reciprocity exponent is $$ \varepsilon(p, q) ;=; \frac{p - 1}{2} \cdot \frac{q - 1}{2} \pmod 2. $$ It equals $0$ unless both $p$ and $q$ are $\equiv 3 (mod 4)$ , in which case it equals $1$ .

Definition (Jacobi symbol; Jacobi 1837). For $n$ an odd positive integer with prime factorisation $n = p_{1}^{e_{1}} \dots p_{k}^{e_{k}}$ and $a$ an integer coprime to $n$ , the Jacobi symbol is the completely multiplicative extension of the Legendre symbol: $$ \left(\frac{a}{n}\right) ;=; \prod_{i = 1}^k \left(\frac{a}{p_i}\right)^{e_i}. $$ For $n = 1$ the Jacobi symbol is defined to equal $+ 1$ . The Jacobi symbol satisfies $(a / n) (b / n) = (ab / n)$ in $a$ and $(a / m) (a / n) = (a / mn)$ in $n$ . It takes values in ${- 1, 0, + 1}$ , with $0$ exactly when $g cd (a, n) > 1$ .

Definition (Frobenius element at a quadratic extension). For $L = Q (p^{*}) / Q$ with $p^{*} = (- 1)^{(p - 1) /2} p$ the signed prime and $q \neq = p$ an odd prime unramified in $L$ , the Frobenius element $Frob_{q} \in Gal (L / Q) = {\pm 1}$ is $+ 1$ if $q$ splits in $L$ and $- 1$ if $q$ remains inert in $L$ . The Artin map sends $q \mapsto Frob_{q}$ , and the splitting behaviour of $q$ in $L$ records the value of the Legendre symbol $(p^{*} / q)$ .

The Jacobi symbol does not detect quadratic residuosity for composite modulus: $(a / n) = + 1$ does not imply $a$ is a square modulo $n$ . For instance $(2/15) = (2/3) (2/5) = (- 1) (- 1) = + 1$ , but $2$ is not a square modulo $15$ (the squares modulo $15$ are ${1, 4, 6, 9, 10}$ ). The right statement is that $a$ is a square modulo $n$ iff $(a / p) = + 1$ for every odd prime $p ∣ n$ and additional conditions hold for the prime $2$ (Hensel-style).

Counterexamples to common slips

"Quadratic reciprocity computes $(a / n)$ for arbitrary $a, n$ ." False: reciprocity in its Gauss form computes $(p / q)$ for distinct odd primes $p, q$ . To compute a general Legendre symbol $(a / p)$ with $a$ composite, one must combine multiplicativity in $a$ — using the supplementary laws for $(- 1/ p)$ and $(2/ p)$ and reciprocity for the odd-prime factors of $a$ — and recurse. The Jacobi-symbol extension makes the recursion work without factoring $a$ at each step, which is the operational advantage.
"The reciprocity exponent depends on the values of $p$ and $q$ themselves." Partially false: the exponent $ε (p, q)$ depends only on the residues of $p$ and $q$ modulo $4$ , not on $p$ and $q$ as integers. Specifically $ε (p, q) = 1$ iff $p \equiv q \equiv 3 (mod 4)$ ; otherwise $ε (p, q) = 0$ . This is why the reciprocity law is sometimes formulated as: $(p / q) = (q / p)$ unless both primes are $\equiv 3 (mod 4)$ .
"The Jacobi symbol $(a / n) = - 1$ implies $a$ is a non-residue modulo $n$ ." True in this direction (since if $a$ were a square modulo $n$ it would be a square modulo every prime divisor $p ∣ n$ , forcing $(a / p) = + 1$ for all $p ∣ n$ , hence $(a / n) = + 1$ ). The converse fails: $(a / n) = + 1$ does not imply $a$ is a square modulo $n$ when $n$ is composite, by the $2 mod 15$ example above.

Key theorem with proof Intermediate+

The signature theorem of this unit is Gauss's quadratic reciprocity law itself. We give the modern textbook proof via Eisenstein's lattice-point counting argument, which is the canonical route in every standard reference (Hardy-Wright Ch. VI, Ireland-Rosen §5.3, Serre Ch. I §3).

Theorem (quadratic reciprocity; Gauss 1801). For distinct odd primes $p, q$ , $$ \left(\frac{p}{q}\right) \left(\frac{q}{p}\right) ;=; (-1)^{\frac{p - 1}{2} \cdot \frac{q - 1}{2}}. $$ Equivalently, $(p / q) = (q / p)$ unless $p \equiv q \equiv 3 (mod 4)$ , in which case $(p / q) = - (q / p)$ .

Proof (Eisenstein 1845 lattice-point counting). Set $P = (p - 1) /2$ and $Q = (q - 1) /2$ for brevity. We compute the product $(p / q) (q / p)$ by counting integer points in the rectangle $R = [1, P] \times [1, Q] \subset Z^{2}$ .

Step 1 — Gauss's lemma applied to $(q / p)$ . From 21.01.06 Exercise 6 (Gauss's lemma), $(q / p) = (- 1)^{μ (q, p)}$ where $μ (q, p)$ counts the elements of ${q, 2 q, \dots, P q}$ whose least positive residue modulo $p$ exceeds $p /2$ . Equivalently, write $j q = p ⌊ j q / p ⌋ + (j q mod p)$ for each $j \in {1, \dots, P}$ ; the residue $j q mod p$ exceeds $p /2$ iff after adjustment by an element of ${p, 2 p, \dots}$ the "absolute residue" representative is negative. A standard counting identity (Gauss 1808, restated in Ireland-Rosen Lemma 5.3.1) gives $$ \mu(q, p) ;\equiv; \sum_{j = 1}^{P} \lfloor j q / p \rfloor \pmod 2. $$ The same identity applied to $(p / q)$ gives $μ (p, q) \equiv \sum_{k = 1}^{Q} ⌊ k p / q ⌋ (mod 2)$ .

Step 2 — Two-way counting of $R$ . The rectangle $R$ contains $P Q$ integer points. We split $R$ by the diagonal line $y = (q / p) x$ — the line from the origin to the opposite corner of $R$ (extended). This diagonal passes through no integer point of $R$ except possibly the corner, but the corner $(P, Q)$ is not on the line (since $Q / P = (q - 1) / (p - 1) \neq = q / p$ for $p \neq = q$ ). Moreover the line $y = (q / p) x$ misses every interior lattice point because if $j q / p = k$ for integers $j, k$ with $1 \leq j \leq P$ , then $p ∣ j q$ , and since $g cd (p, q) = 1$ we have $p ∣ j$ , impossible for $j \leq P < p$ .

So every lattice point of $R$ lies strictly above or strictly below the diagonal. The number of lattice points strictly below the diagonal (i.e., with $y < (q / p) x$ , equivalently $p y < q x$ ) is $$ N_{\text{below}} ;=; \sum_{x = 1}^{P} #{y : 1 \leq y \leq Q, ; p y < q x} ;=; \sum_{x = 1}^{P} \min(Q, \lfloor q x / p \rfloor). $$ For $x \leq P = (p - 1) /2$ we have $q x / p \leq q P / p = q (p - 1) / (2 p) < q /2 < Q + 1$ , so $⌊ q x / p ⌋ \leq Q$ , and the $min$ is unneeded: $$ N_{\text{below}} ;=; \sum_{x = 1}^{P} \lfloor q x / p \rfloor ;\equiv; \mu(q, p) \pmod 2. $$

Symmetrically, the number of lattice points strictly above the diagonal is $$ N_{\text{above}} ;=; \sum_{y = 1}^{Q} \lfloor p y / q \rfloor ;\equiv; \mu(p, q) \pmod 2. $$

Step 3 — Add. $N_{below} + N_{above} = P Q$ , the total point count of $R$ . Reducing modulo $2$ : $$ \mu(q, p) + \mu(p, q) ;\equiv; P Q ;=; \frac{p - 1}{2} \cdot \frac{q - 1}{2} \pmod 2. $$

Step 4 — Combine via Gauss's lemma. By Gauss's lemma, $$ \left(\frac{p}{q}\right) \left(\frac{q}{p}\right) ;=; (-1)^{\mu(p, q)} (-1)^{\mu(q, p)} ;=; (-1)^{\mu(p, q) + \mu(q, p)} ;=; (-1)^{\frac{p - 1}{2} \cdot \frac{q - 1}{2}}. $$ This is the law of quadratic reciprocity. $□$

Bridge. Quadratic reciprocity is the foundational example of a reciprocity law — a relation that ties the splitting behaviour of a prime $q$ in an extension $L / K$ (or equivalently, the value of a residue symbol at $q$ ) to a congruence condition on $q$ modulo the conductor of the extension. The central insight is that the quadratic-residuosity question $q \in QR_{p}$ depends only on the residue class of $q$ modulo $4 p$ , with the dependence given by the Legendre symbol $(q / p)$ and the supplementary laws — the analogue for the quadratic extension $Q (p^{*}) / Q$ of the statement of class field theory. The bridge is to the broader framework of 21.02.05 class field theory and Artin reciprocity, where the Artin map identifies the abelianised Galois group with a generalised ideal class group, and the Frobenius at $q$ records the splitting of $q$ in $L$ .

The Hilbert symbol formulation (Hilbert 1897) gives the cleanest packaging: the Hilbert symbol $(a, b)_{v}$ at each place $v$ of $Q$ detects local solvability of $a x^{2} + b y^{2} = z^{2}$ , and the global product formula $\prod_{v} (a, b)_{v} = 1$ is logically equivalent to quadratic reciprocity together with the two supplementary laws. Putting these together, the elementary law that $p$ is a square modulo $q$ exactly when $q$ is a square modulo $p$ (up to the parity correction for $p \equiv q \equiv 3 (mod 4)$ ) is the simplest manifestation of a structural principle that generalises through cubic and biquadratic reciprocity in cyclotomic integer rings (Eisenstein 1844), Eisenstein reciprocity for $ℓ$ -th powers (Furtwängler 1909), Artin reciprocity for abelian extensions (Artin 1927), and the Langlands programme for non-abelian extensions.

Exercises Intermediate+

Exercise 1 (easy, numeric).

Compute the Legendre symbol $(7/19)$ using quadratic reciprocity. Enter $+ 1$ , $- 1$ , or $0$ .

Hint

Both $7$ and $19$ are $\equiv 3 (mod 4)$ , so reciprocity flips: $(7/19) = - (19/7)$ . Reduce $19 \equiv 5 (mod 7)$ and compute $(5/7)$ .

Answer

$+ 1$ . Both $7 \equiv 3 (mod 4)$ and $19 \equiv 3 (mod 4)$ , so reciprocity gives $(7/19) (19/7) = (- 1)^{3 \cdot 9} = - 1$ , hence $(7/19) = - (19/7)$ .

Reduce $19 \equiv 5 (mod 7)$ , so $(19/7) = (5/7)$ . Apply reciprocity to $(5/7)$ : $5 \equiv 1 (mod 4)$ and $7 \equiv 3 (mod 4)$ , so the flip exponent $2 \cdot 3 = 6$ is even and $(5/7) = (7/5)$ . Reduce $7 \equiv 2 (mod 5)$ , so $(7/5) = (2/5)$ . Apply the second supplementary law: $5 \equiv 5 (mod 8)$ , so $(2/5) = - 1$ .

Combine: $(19/7) = (5/7) = (7/5) = (2/5) = - 1$ , hence $(7/19) = - (- 1) = + 1$ . Cross-check by enumeration: the squares modulo $19$ are ${1, 4, 5, 6, 7, 9, 11, 16, 17}$ , and $7$ is on the list (since $8^{2} = 64 = 3 \cdot 19 + 7$ ), confirming $(7/19) = + 1$ .

Exercise 3 (medium, numeric).

Compute the Legendre symbol $(73/127)$ using the reciprocity algorithm. Enter $+ 1$ , $- 1$ , or $0$ .

Hint

$73$ and $127$ are both odd primes. Check their residues modulo $4$ , apply reciprocity to flip, reduce the larger modulo the smaller, and recurse.

Answer

$+ 1$ . Both $73 \equiv 1 (mod 4)$ and $127 \equiv 3 (mod 4)$ . The flip exponent is $36 \cdot 63 = 2268$ , even (because $73 - 1 = 72$ is divisible by $4$ , so $(73 - 1) /2 = 36$ is even). Hence $(73/127) = (127/73)$ .

Reduce $127 \equiv 54 (mod 73)$ , so $(127/73) = (54/73) = (2/73) (27/73) = (2/73) (3/73)^{3} = (2/73) (3/73)$ since $(3/73)^{2} = 1$ .

Compute $(2/73)$ : $73 \equiv 1 (mod 8)$ , so the second supplementary law gives $(2/73) = + 1$ .

Compute $(3/73)$ : $3 \equiv 3 (mod 4)$ and $73 \equiv 1 (mod 4)$ , so the flip exponent is even and $(3/73) = (73/3)$ . Reduce $73 \equiv 1 (mod 3)$ , so $(73/3) = (1/3) = + 1$ .

Combine: $(54/73) = (2/73) (3/73) = (+ 1) (+ 1) = + 1$ , so $(127/73) = + 1$ , hence $(73/127) = + 1$ . So $73$ is a square modulo $127$ . (Direct check: $3 2^{2} = 1024 = 8 \cdot 127 + 8$ — not $73$ — $5 0^{2} = 2500 = 19 \cdot 127 + 87$ , $5 8^{2} = 3364 = 26 \cdot 127 + 62$ , $6 4^{2} = 4096 = 32 \cdot 127 + 32$ ; a brute search would find a square root eventually, but the reciprocity algorithm answered the existence question in seconds.)

Exercise 4 (medium, symbolic).

Prove that the Jacobi-symbol reciprocity law holds: for $m, n$ odd coprime positive integers, $$ \left(\frac{m}{n}\right) \left(\frac{n}{m}\right) ;=; (-1)^{\frac{m - 1}{2} \cdot \frac{n - 1}{2}}. $$

Hint

Factor $m = \prod p_{i}^{a_{i}}$ and $n = \prod q_{j}^{b_{j}}$ and expand $(m / n) (n / m)$ as a product over prime pairs using the multiplicative property of the Jacobi symbol. Then apply quadratic reciprocity to each prime pair.

Answer

Factor $m = \prod_{i} p_{i}^{a_{i}}$ and $n = \prod_{j} q_{j}^{b_{j}}$ with distinct odd primes $p_{i}, q_{j}$ (coprime by hypothesis). By the multiplicative property of the Jacobi symbol, $$ \left(\frac{m}{n}\right) ;=; \prod_{i, j} \left(\frac{p_i}{q_j}\right)^{a_i b_j}, \qquad \left(\frac{n}{m}\right) ;=; \prod_{i, j} \left(\frac{q_j}{p_i}\right)^{a_i b_j}. $$ Hence $$ \left(\frac{m}{n}\right) \left(\frac{n}{m}\right) ;=; \prod_{i, j} \left[\left(\frac{p_i}{q_j}\right) \left(\frac{q_j}{p_i}\right)\right]^{a_i b_j} ;=; \prod_{i, j} (-1)^{a_i b_j \cdot \frac{p_i - 1}{2} \cdot \frac{q_j - 1}{2}} $$ by Gauss's quadratic reciprocity applied to each pair $(p_{i}, q_{j})$ .

We must show the exponent $$ E ;=; \sum_{i, j} a_i b_j \cdot \frac{p_i - 1}{2} \cdot \frac{q_j - 1}{2} $$ is congruent modulo $2$ to $((m - 1) /2) ((n - 1) /2)$ .

The key identity: for any odd positive integer $N = \prod p_{i}^{a_{i}}$ , $$ \frac{N - 1}{2} ;\equiv; \sum_i a_i \cdot \frac{p_i - 1}{2} \pmod 2. $$ Proof of the identity. For each odd prime power $p^{a}$ , an induction on $a$ shows $(p^{a} - 1) /2 \equiv a (p - 1) /2 (mod 2)$ : the base case $a = 1$ is immediate, and the step $p^{a + 1} - 1 = (p - 1) (p^{a} + p^{a - 1} + \dots + 1) = (p^{a} - 1) + p^{a} (p - 1)$ gives $(p^{a + 1} - 1) /2 = (p^{a} - 1) /2 + p^{a} (p - 1) /2 \equiv (a + 1) (p - 1) /2 (mod 2)$ since $p^{a}$ is odd. For a product $N = N_{1} N_{2}$ of odd positive integers, $N - 1 = (N_{1} - 1) + (N_{2} - 1) + (N_{1} - 1) (N_{2} - 1)$ , and the last term is divisible by $4$ (product of two even numbers $(N_{1} - 1), (N_{2} - 1)$ ), so $(N - 1) /2 \equiv (N_{1} - 1) /2 + (N_{2} - 1) /2 (mod 2)$ . Combining gives the identity for general $N$ .

By the identity, $(m - 1) /2 \equiv \sum_{i} a_{i} (p_{i} - 1) /2 (mod 2)$ and $(n - 1) /2 \equiv \sum_{j} b_{j} (q_{j} - 1) /2 (mod 2)$ , so $$ \frac{m - 1}{2} \cdot \frac{n - 1}{2} ;\equiv; \left(\sum_i a_i \frac{p_i - 1}{2}\right) \left(\sum_j b_j \frac{q_j - 1}{2}\right) ;=; E \pmod 2. $$ Substituting back, $$ \left(\frac{m}{n}\right) \left(\frac{n}{m}\right) ;=; (-1)^E ;=; (-1)^{\frac{m - 1}{2} \cdot \frac{n - 1}{2}}. $$

Rubric: full credit for the multiplicative expansion, the identity $(N - 1) /2 \equiv \sum a_{i} (p_{i} - 1) /2 (mod 2)$ , and the substitution.

Exercise 5 (medium, symbolic).

Prove the Jacobi-symbol supplementary laws for $n$ odd positive: $$ \left(\frac{-1}{n}\right) ;=; (-1)^{(n - 1)/2}, \qquad \left(\frac{2}{n}\right) ;=; (-1)^{(n^2 - 1)/8}. $$

Hint

Use multiplicativity in the prime factorisation of $n$ and the Legendre-symbol supplementary laws. The identity $(N - 1) /2 \equiv \sum a_{i} (p_{i} - 1) /2 (mod 2)$ from Exercise 4 is the lever for the first law; for the second, use the analogous identity $(N^{2} - 1) /8 \equiv \sum a_{i} (p_{i}^{2} - 1) /8 (mod 2)$ .

Answer

Factor $n = \prod_{i} p_{i}^{a_{i}}$ . By multiplicativity and the Legendre supplementary laws, $$ \left(\frac{-1}{n}\right) ;=; \prod_i \left(\frac{-1}{p_i}\right)^{a_i} ;=; \prod_i (-1)^{a_i (p_i - 1)/2} ;=; (-1)^{\sum_i a_i (p_i - 1)/2}. $$ By the identity from Exercise 4, $\sum_{i} a_{i} (p_{i} - 1) /2 \equiv (n - 1) /2 (mod 2)$ , so $(- 1/ n) = (- 1)^{(n - 1) /2}$ .

For the second supplementary law, $$ \left(\frac{2}{n}\right) ;=; \prod_i \left(\frac{2}{p_i}\right)^{a_i} ;=; \prod_i (-1)^{a_i (p_i^2 - 1)/8} ;=; (-1)^{\sum_i a_i (p_i^2 - 1)/8}. $$

We need $\sum_{i} a_{i} (p_{i}^{2} - 1) /8 \equiv (n^{2} - 1) /8 (mod 2)$ . The analogous identity: for $N = N_{1} N_{2}$ odd, $N^{2} - 1 = N_{1}^{2} N_{2}^{2} - 1 = (N_{1}^{2} - 1) + N_{1}^{2} (N_{2}^{2} - 1)$ , so $(N^{2} - 1) /8 \equiv (N_{1}^{2} - 1) /8 + (N_{2}^{2} - 1) /8 (mod 2)$ (using that $N_{1}^{2}$ is an odd square, $\equiv 1 (mod 8)$ , so $N_{1}^{2} (N_{2}^{2} - 1) \equiv N_{2}^{2} - 1 (mod 16)$ ). Induction on $a$ gives $(p^{a})^{2} - 1 = p^{2 a} - 1$ and a similar argument shows $(p^{2 a} - 1) /8 \equiv a (p^{2} - 1) /8 (mod 2)$ . Combining the prime-power identity and the product identity gives $\sum_{i} a_{i} (p_{i}^{2} - 1) /8 \equiv (n^{2} - 1) /8 (mod 2)$ .

Hence $(2/ n) = (- 1)^{(n^{2} - 1) /8}$ .

Rubric: full credit for both multiplicative-expansion arguments, the prime-power identity for $(p^{a} - 1) /2$ and $(p^{2 a} - 1) /8$ , and the multiplicativity-mod-2 identities for $(N - 1) /2$ and $(N^{2} - 1) /8$ .

Exercise 6 (medium, symbolic).

Use quadratic reciprocity to prove: an odd prime $p$ is a quadratic residue modulo every prime $q \neq = p$ with $q \equiv 1 (mod 4 p)$ .

Hint

For $q \equiv 1 (mod 4 p)$ , the Legendre symbol $(p / q)$ depends only on the residue $q (mod 4 p)$ by quadratic reciprocity and the supplementary laws. Compute $(p / q)$ explicitly for $q \equiv 1 (mod 4 p)$ .

Answer

Let $p$ be an odd prime and $q$ a prime with $q \neq = p$ and $q \equiv 1 (mod 4 p)$ . In particular $q \equiv 1 (mod 4)$ , so the reciprocity flip exponent $((p - 1) /2) ((q - 1) /2)$ is even, and quadratic reciprocity gives $(p / q) = (q / p)$ .

Since $q \equiv 1 (mod p)$ (which follows from $q \equiv 1 (mod 4 p)$ stripped of the factor $4$ ), the Legendre symbol $(q / p) = (1/ p) = + 1$ (since $1 = 1^{2}$ is a square).

Hence $(p / q) = + 1$ and $p$ is a quadratic residue modulo $q$ .

The result is a special case of the general fact that the Legendre symbol $(p / q)$ depends only on the residue class of $q$ modulo $4 p$ (or modulo $p$ when $p \equiv 1 (mod 4)$ , by the reciprocity-without-flip case). This is the reason quadratic reciprocity is a reciprocity law in the modern sense: it identifies the value of an arithmetic symbol $(p / q)$ with the residue class of $q$ modulo a conductor (here $4 p$ ). The class-field-theoretic interpretation: the splitting of $q$ in $Q (p^{*}) / Q$ depends only on $q (mod 4 p)$ since the conductor of this extension divides $4 p$ .

Applications include: prime divisors of values of integer polynomials $f (x) \in Z [x]$ are congruent to specific residues modulo the discriminant of $f$ ; Dirichlet's theorem on primes in arithmetic progressions interacts with QR to determine the density of primes that are residues of a fixed integer.

Rubric: full credit for collapsing the reciprocity flip and the reduction $q \equiv 1 (mod p)$ .

Exercise 7 (hard, symbolic).

Sketch Gauss's third proof of quadratic reciprocity, via Gauss's lemma and the absolute-residue counting. Show that for distinct odd primes $p, q$ , the parities of $μ (p, q)$ and $μ (q, p)$ add modulo $2$ to $((p - 1) /2) ((q - 1) /2) (mod 2)$ , where $μ (p, q)$ is the Gauss-lemma count for $(p / q)$ .

Hint

This is essentially the Eisenstein lattice-point proof above, stated in the original Gaussian language of counting residues. Reframe the lattice-point count as a count of "large absolute residues" of multiples of $q$ modulo $p$ , and verify the identity $μ (q, p) \equiv \sum_{j} ⌊ j q / p ⌋ (mod 2)$ that bridges the two formulations.

Answer

Write $P = (p - 1) /2$ , $Q = (q - 1) /2$ . For each $j \in {1, \dots, P}$ , write $j q = p ⌊ j q / p ⌋ + r_{j}$ with $r_{j} \in {1, \dots, p - 1}$ the residue. Gauss's lemma counts $μ (q, p) = # {j : r_{j} > p /2}$ .

We compute the parities. The sum $\sum_{j = 1}^{P} j q = q (P) (P + 1) /2 = q P (P + 1) /2$ equals $p \sum_{j} ⌊ j q / p ⌋ + \sum_{j} r_{j}$ . Reduce modulo $2$ : $$ q \cdot \frac{P(P + 1)}{2} ;\equiv; \sum_j \lfloor j q / p \rfloor + \sum_j r_j \pmod 2, $$ since $p$ is odd.

Now $\sum_{j} r_{j}$ is a sum over a set that splits as ${r_{j} : r_{j} \leq P} \cup {r_{j} : r_{j} > P}$ . By the permutation argument of Gauss's lemma (Exercise 6 of 21.01.06), the small-residue values ${r_{j} : r_{j} \leq P}$ together with the reflected large-residue values ${p - r_{j} : r_{j} > P}$ form a permutation of ${1, 2, \dots, P}$ . So $\sum_{j} r_{j} = (small r_{j}) + (large r_{j}) = \sum_{k = 1}^{P} k - 2 \cdot (small r_{j}) + p \cdot μ (q, p) + 2 \cdot (small r_{j}) - 2 \cdot (small r_{j})$ … the cleanest restatement: $\sum_{j} r_{j} \equiv P (P + 1) /2 + p \cdot μ (q, p) (mod 2)$ , since the reflections $r_{j} \mapsto p - r_{j}$ change the sum by $p \cdot μ (q, p)$ modulo the small-residue rearrangement, and $p \equiv 1 (mod 2)$ .

Reducing: $\sum_{j} r_{j} \equiv P (P + 1) /2 + μ (q, p) (mod 2)$ .

Substituting: $$ q \cdot \frac{P(P + 1)}{2} ;\equiv; \sum_j \lfloor j q / p \rfloor + \frac{P(P + 1)}{2} + \mu(q, p) \pmod 2. $$ So $μ (q, p) \equiv \sum_{j} ⌊ j q / p ⌋ + (q - 1) P (P + 1) /2 (mod 2)$ . Since $q$ is odd, $(q - 1) /2$ is an integer; and $P (P + 1) /2$ is an integer (consecutive integers' product divisible by $2$ ). Modulo $2$ , the term $(q - 1) P (P + 1) /2 = 2 \cdot ((q - 1) /2) \cdot P (P + 1) /2 \equiv 0 (mod 2)$ . Hence $$ \mu(q, p) ;\equiv; \sum_{j = 1}^{P} \lfloor j q / p \rfloor \pmod 2, $$ the identity used in Step 1 of the Key Theorem proof.

Symmetrically $μ (p, q) \equiv \sum_{k = 1}^{Q} ⌊ k p / q ⌋ (mod 2)$ . By the lattice-point two-way counting (Step 2 of the Key Theorem), $$ \sum_{j = 1}^{P} \lfloor j q / p \rfloor + \sum_{k = 1}^{Q} \lfloor k p / q \rfloor ;=; P Q, $$ so $μ (q, p) + μ (p, q) \equiv P Q (mod 2)$ . Combining with Gauss's lemma $(p / q) (q / p) = (- 1)^{μ (p, q) + μ (q, p)}$ yields quadratic reciprocity.

This is Gauss's third proof in the form he published in Theorematis arithmetici demonstratio nova (1808): the lemma and counting tradition that Eisenstein 1845 reformulated as the geometric lattice-point counting argument.

Rubric: full credit for the residue-sum identity, the parity reduction of $\sum_{j} r_{j}$ , and the cross-check with the lattice-point count.

Exercise 8 (hard, symbolic).

Sketch the Gauss-sum proof of quadratic reciprocity. The quadratic Gauss sum modulo $p$ is $$ \tau(\chi_p) ;=; \sum_{a = 1}^{p - 1} \left(\frac{a}{p}\right) \zeta_p^a, \qquad \zeta_p = e^{2 \pi i / p}. $$ Use the evaluation $τ (χ_{p})^{2} = (- 1)^{(p - 1) /2} p$ and the eighth-power computation $τ (χ_{p})^{q} \equiv τ (χ_{p}) \cdot (q / p) (mod q)$ to derive reciprocity.

Hint

The Gauss sum lives in the cyclotomic field $Q (ζ_{p})$ . Raise to the $q$ -th power using the Frobenius automorphism $ζ_{p} \mapsto ζ_{p}^{q}$ at $q$ , and compare to the value of $τ (χ_{p})$ raised to the $q$ -th power using the Gauss-sum quadratic identity.

Answer

Work in the ring $Z [ζ_{p}]$ of cyclotomic integers and its reduction modulo $q$ . The Gauss-sum identity $τ (χ_{p})^{2} = (- 1)^{(p - 1) /2} p =: p^{*}$ holds in $Z [ζ_{p}]$ (Gauss 1805 evaluation). Let $τ = τ (χ_{p})$ for brevity, so $τ^{2} = p^{*}$ .

Raise $τ$ to the $q$ -th power modulo $q$ : $$ \tau^q ;=; \left(\sum_a \chi_p(a) \zeta_p^a\right)^q ;\equiv; \sum_a \chi_p(a)^q \zeta_p^{a q} \pmod q, $$ by the Frobenius identity $(x + y)^{q} \equiv x^{q} + y^{q} (mod q)$ in $F_{q} [ζ_{p}]$ . Since $χ_{p} (a) = \pm 1$ has $χ_{p} (a)^{q} = χ_{p} (a)$ (as $q$ is odd), the sum becomes $$ \tau^q ;\equiv; \sum_a \chi_p(a) \zeta_p^{a q} ;=; \sum_a \chi_p(a q^{-1}) \zeta_p^{a} ;=; \chi_p(q^{-1}) \tau ;=; \chi_p(q) \tau \pmod q, $$ substituting $a \mapsto a q^{- 1}$ in the sum (a permutation of $F_{p}^{\times}$ ) and using $χ_{p} (q^{- 1}) = χ_{p} (q)^{- 1} = χ_{p} (q)$ .

On the other hand, $τ^{q} = τ \cdot τ^{q - 1} = τ \cdot (τ^{2})^{(q - 1) /2} = τ \cdot (p^{*})^{(q - 1) /2}$ . By Euler's criterion modulo $q$ , $(p^{*})^{(q - 1) /2} \equiv (p^{*} / q) (mod q)$ .

Combining: $τ \cdot (p^{*} / q) \equiv χ_{p} (q) τ (mod q)$ . Multiplying through by $τ$ and using $τ^{2} = p^{*}$ (coprime to $q$ since $p \neq = q$ ), $$ p^* \cdot \left(\frac{p^}{q}\right) ;\equiv; \chi_p(q) \cdot p^ \pmod q, $$ hence $(p^{*} / q) \equiv χ_{p} (q) = (q / p) (mod q)$ . Both sides are in ${- 1, + 1}$ and $q \geq 3$ , so $(p^{*} / q) = (q / p)$ as integers.

Expand $p^{*} = (- 1)^{(p - 1) /2} p$ using multiplicativity: $$ \left(\frac{p^*}{q}\right) ;=; \left(\frac{(-1)^{(p - 1)/2}}{q}\right) \left(\frac{p}{q}\right) ;=; \left(\frac{-1}{q}\right)^{(p - 1)/2} \left(\frac{p}{q}\right) ;=; (-1)^{\frac{p - 1}{2} \cdot \frac{q - 1}{2}} \left(\frac{p}{q}\right), $$ using the first supplementary law $(- 1/ q) = (- 1)^{(q - 1) /2}$ .

So $(q / p) = (- 1)^{((p - 1) /2) ((q - 1) /2)} (p / q)$ , which rearranges to $$ \left(\frac{p}{q}\right) \left(\frac{q}{p}\right) ;=; (-1)^{\frac{p - 1}{2} \cdot \frac{q - 1}{2}}. $$ This is quadratic reciprocity. The proof is due to Gauss (1818, fourth proof) and was the foundation for all later $L$ -function and Gauss-sum-based proofs (Dirichlet 1854, Hecke 1923 in higher arithmetic).

Rubric: full credit for the Frobenius modulo $q$ , the Euler-criterion application, the multiplicativity expansion of $p^{*}$ , and the rearrangement to QR.

Lean formalization Intermediate+

Mathlib provides the canonical scaffolding for quadratic reciprocity and its supplementary laws, with the proofs going through Gauss sums (the algebraic-number-theory route).

-- Operative imports: Mathlib.NumberTheory.LegendreSymbol.QuadraticReciprocity,
-- Mathlib.NumberTheory.LegendreSymbol.GaussSum,
-- Mathlib.NumberTheory.LegendreSymbol.JacobiSymbol

#check @ZMod.quadraticReciprocity
-- (p/q) * (q/p) = (-1)^((p - 1)/2 * (q - 1)/2), the main reciprocity law.

#check @ZMod.quadraticReciprocity_one_mod_four
-- Specialised statement for the p ≡ 1 (mod 4) case (no flip).

#check @ZMod.quadraticReciprocity_three_mod_four_three_mod_four
-- Specialised statement for the p ≡ q ≡ 3 (mod 4) case (flip).

#check @ZMod.legendreSym_two
-- (2/p) = (-1)^((p^2 - 1)/8), the second supplementary law.

#check @ZMod.legendreSym_neg_one
-- (-1/p) = (-1)^((p - 1)/2), the first supplementary law.

#check @ZMod.jacobiSym
-- The Jacobi symbol (a/n) for n odd positive.

#check @ZMod.jacobiSym_quadraticReciprocity
-- (m/n) * (n/m) = (-1)^((m - 1)/2 * (n - 1)/2) for m, n odd coprime positive.

#check @gaussSum_sq
-- The evaluation tau(chi_p)^2 = (-1)^((p - 1)/2) * p of the quadratic Gauss sum.

The Mathlib formalisation is comprehensive at the level of the reciprocity statement, both supplementary laws, the Jacobi-symbol generalisation with its own reciprocity law, and the underlying Gauss-sum machinery. What Mathlib has not yet packaged: a constructive Eisenstein lattice-point counting proof (Mathlib's proof uses Gauss sums and is non-constructive in style); the explicit binary Jacobi-symbol $O ((lo g n)^{2})$ algorithm with constructive output; the Hilbert-symbol product formula $\prod_{v} (a, b)_{v} = 1$ as a packaged reciprocity result; cubic and biquadratic reciprocity in $Z [ζ_{3}]$ and $Z [i]$ ; the Artin reciprocity map for the quadratic extension $Q (p^{*}) / Q$ with the Frobenius identification $Frob_{q} \mapsto (p^{*} / q)$ . These are the formalisation gaps documented in the unit metadata Mathlib gap analysis.

Advanced results Master

Theorem 1 (quadratic reciprocity; Gauss 1801, theorema aureum). For distinct odd primes $p, q$ , $$ \left(\frac{p}{q}\right) \left(\frac{q}{p}\right) ;=; (-1)^{\frac{p - 1}{2} \cdot \frac{q - 1}{2}}. $$ Equivalently $(p / q) = (q / p)$ unless $p \equiv q \equiv 3 (mod 4)$ , in which case $(p / q) = - (q / p)$ ^{[Gauss 1801]}. Proved above as the Key Theorem via Eisenstein's lattice-point counting. Gauss called the law the theorema aureum — "the golden theorem" — and announced his first complete proof in his mathematical diary entry of 19 April 1796 ("Per inductionem inveni 24 Mart. 1796"). The 1801 Disquisitiones proof is Gauss's first; he produced seven more proofs over his lifetime ^{[Gauss 1808]} ^{[Gauss 1818]}, collected in Werke II 1863.

Theorem 2 (first supplementary law). For $p$ an odd prime, $(- 1/ p) = (- 1)^{(p - 1) /2}$ , i.e., $(- 1/ p) = + 1$ iff $p \equiv 1 (mod 4)$ ^{[Gauss 1801]}. Proved in 21.01.06 Exercise 5 via Euler's criterion. The first supplementary law characterises the primes for which $- 1$ is a square modulo $p$ , which is also the characterisation of primes representable as $p = a^{2} + b^{2}$ (Fermat 1640, Euler 1755).

Theorem 3 (second supplementary law). For $p$ an odd prime, $(2/ p) = (- 1)^{(p^{2} - 1) /8}$ , i.e., $(2/ p) = + 1$ iff $p \equiv \pm 1 (mod 8)$ and $(2/ p) = - 1$ iff $p \equiv \pm 3 (mod 8)$ ^{[Gauss 1801]}. Proved in 21.01.06 Exercise 7 via Gauss's lemma applied to $a = 2$ . The second supplementary law together with the first and quadratic reciprocity gives a complete algorithm for computing $(a / p)$ for any $a$ and any odd prime $p$ .

Theorem 4 (Jacobi-symbol reciprocity; Jacobi 1837). For $m, n$ odd coprime positive integers, $$ \left(\frac{m}{n}\right) \left(\frac{n}{m}\right) ;=; (-1)^{\frac{m - 1}{2} \cdot \frac{n - 1}{2}}, $$ together with the Jacobi-symbol supplementary laws $(- 1/ n) = (- 1)^{(n - 1) /2}$ and $(2/ n) = (- 1)^{(n^{2} - 1) /8}$ ^{[Lemmermeyer 2000]}. Proved above as Exercises 4 and 5 via the multiplicativity identity $(N - 1) /2 \equiv \sum a_{i} (p_{i} - 1) /2 (mod 2)$ and its $(N^{2} - 1) /8$ analogue. The Jacobi-symbol formulation is the operative form for the binary Jacobi-symbol algorithm: compute $(a / n)$ in $O ((lo g n)^{2})$ time by alternating reduction $a mod n$ and reciprocity flip without factoring $n$ .

Theorem 5 (Hilbert reciprocity; Hilbert 1897). For $a, b \in Q^{\times}$ , the Hilbert symbol $(a, b)_{v} \in {\pm 1}$ at each place $v$ of $Q$ (finite primes and the archimedean place $\infty$ ) records whether the quadratic form $Z^{2} - a X^{2} - b Y^{2}$ has a non-zero solution in $Q_{v}$ . The product formula holds: $$ \prod_v (a, b)_v ;=; 1, $$ with all but finitely many factors equal to $+ 1$ ^{[Hilbert 1897]}. For $a, b$ both squarefree positive integers coprime to a prime $p$ , the Hilbert symbol $(a, b)_{p}$ at the finite place $p$ reduces to a Legendre-symbol expression — specifically, for $u, v \in Z_{p}^{\times}$ units, $(u, p)_{p} = (\overset{u}{ˉ} / p)$ where $\overset{u}{ˉ}$ is the reduction modulo $p$ . The product formula encodes quadratic reciprocity in adelic form: the matching of signs at the two finite primes $p, q$ and the archimedean place $\infty$ gives precisely $(p / q) (q / p) = (- 1)^{((p - 1) /2) ((q - 1) /2)}$ . Hilbert's Zahlbericht developed this in §§64-90, and Hilbert's 9th problem (1900 ICM Paris) ^{[Hilbert 1900]} asked for the most general reciprocity law in any algebraic number field — the question answered by Takagi 1920 and Artin 1927.

Theorem 6 (Eisenstein reciprocity for $ℓ$ -th power residues; Eisenstein 1850 / Furtwängler 1909). Let $ℓ$ be an odd prime and $ζ_{ℓ} = e^{2 π i / ℓ}$ . For $α \in Z [ζ_{ℓ}]$ coprime to $ℓ$ and $a \in Z$ a rational integer coprime to $ℓ α$ , the $ℓ$ -th power residue symbol $(α / a)_{ℓ} \in μ_{ℓ}$ (the group of $ℓ$ -th roots of unity) satisfies $$ \left(\frac{\alpha}{a}\right)\ell ;=; \left(\frac{a}{\alpha}\right)\ell $$ provided $α$ is primary ( $α \equiv$ rational mod $(1 - ζ_{ℓ})^{2}$ ) ^{[Furtwängler 1909]}. Eisenstein stated this in 1850 Crelle 39 for $ℓ = 3$ extending his 1844 cubic reciprocity, and Furtwängler 1909 Math. Ann. 67 proved the full $ℓ$ -th-power form. Eisenstein reciprocity is the natural generalisation of Gauss's quadratic reciprocity from $Z$ to cyclotomic integer rings $Z [ζ_{ℓ}]$ , and was the bridge between the elementary reciprocity laws and the general class-field-theoretic reciprocity of Takagi 1920 and Artin 1927.

Theorem 7 (Artin reciprocity; Artin 1927). For $L / K$ a finite abelian extension of number fields with modulus $m$ , the Artin map $$ \mathrm{Art}{L/K} : I_K(\mathfrak{m}) / N{L/K}(I_L(\mathfrak{m})) P_{L/K}(\mathfrak{m}) ;\xrightarrow{\sim}; \mathrm{Gal}(L/K) $$ is an isomorphism, sending an unramified prime $p$ of $K$ to its Frobenius element $Frob_{p} \in Gal (L / K)$ ^{[Artin 1927]}. Specialised to the quadratic extension $L = Q (p^{*}) / Q$ where $p^{*} = (- 1)^{(p - 1) /2} p$ is the signed prime, the Artin map sends an odd prime $q \neq = p$ to the Frobenius $Frob_{q}$ , whose image in $Gal (L / Q) ≅ {\pm 1}$ is $(p^{*} / q)$ . The Artin map's compatibility with the conductor $m = (4 p)$ recovers quadratic reciprocity: the value of $(p^{*} / q)$ depends only on the residue class of $q$ modulo $4 p$ . Takagi 1920 J. Coll. Sci. Tokyo 41 had proved existence of the abelian-extension classification; Artin 1927 Hamb. Abh. 5 added the explicit Frobenius-isomorphism formulation. The non-abelian generalisation is the Langlands programme.

Theorem 8 (Stickelberger's theorem; Stickelberger 1890). In the cyclotomic field $Q (ζ_{p})$ , the prime ideal factorisation of the Gauss sum $τ (χ_{p})$ is controlled by the Stickelberger element $$ \theta ;=; \sum_{a = 1}^{p - 1} \left{\frac{a}{p}\right} \sigma_a^{-1} \in \mathbb{Q}[\mathrm{Gal}(\mathbb{Q}(\zeta_p)/\mathbb{Q})], $$ where ${x}$ is the fractional part of $x$ and $σ_{a}$ is the Galois automorphism $ζ_{p} \mapsto ζ_{p}^{a}$ . The Stickelberger ideal $θ \cdot Z [Gal]$ annihilates the ideal class group of $Q (ζ_{p})$ . Stickelberger 1890 Math. Ann. 37 generalises the Gauss-sum proof of quadratic reciprocity to a much broader class-field-theoretic framework, and is the foundation for Iwasawa theory (Iwasawa 1959).

Synthesis. Quadratic reciprocity is the foundational structural theorem of elementary number theory and the prototype of every subsequent reciprocity law. The central insight is exactly that the quadratic-residuosity question $q \in QR_{p}$ depends only on the residue class of $q$ modulo the conductor $4 p$ of the quadratic extension $Q (p^{*}) / Q$ — the Legendre symbol $(p^{*} / q)$ is the Artin map evaluated at $q$ . The bridge is to the broader framework of 21.02.05 class field theory, where the Artin map identifies the abelianised Galois group with a generalised ideal class group, and to the Hilbert-symbol formulation of 21.03.04 adelic reciprocity, where the global product formula $\prod_{v} (a, b)_{v} = 1$ packages quadratic reciprocity and the two supplementary laws into a single adelic statement. Putting these together, the elementary law $(p / q) (q / p) = (- 1)^{((p - 1) /2) ((q - 1) /2)}$ is the rational-prime manifestation of a structural principle that generalises through Eisenstein reciprocity for $ℓ$ -th powers (Eisenstein 1850, Furtwängler 1909), Artin reciprocity for abelian extensions (Takagi 1920, Artin 1927), and the Langlands programme for non-abelian extensions (Langlands 1967, Wiles-Taylor 1995).

The historical arc from Euler 1744 to Artin 1927 is the canonical example of how an elementary observation grows into a structural principle. Euler 1744 Comm. Acad. Petrop. 14 conjectured special cases of quadratic reciprocity disguised as theorems about divisors of binary quadratic forms $p a^{2} + q b^{2}$ ; Legendre 1798 Essai sur la théorie des nombres gave the modern symbol-form statement with an incomplete proof depending on the unproven Dirichlet theorem on primes in arithmetic progressions; Gauss 1801 articles 125-152 gave the first complete proof, by induction on the larger prime, and then produced seven more proofs ^{[Gauss 1808]} ^{[Gauss 1818]} over the next two decades. Jacobi 1837 extended to the Jacobi symbol with the algorithmic consequence of efficient computation; Eisenstein 1844 added cubic and biquadratic reciprocity in the cyclotomic rings; Eisenstein 1845 ^{[Eisenstein 1845]} gave the lattice-point-counting proof that became the canonical textbook proof. Dirichlet 1854 / Dedekind 1894 gave the Gauss-sum proof via cyclotomic fields. Hilbert 1897 generalised to the Hilbert symbol and the product formula, with the 9th Hilbert problem (1900) asking for the most general reciprocity. Furtwängler 1909 proved Eisenstein reciprocity for $ℓ$ -th powers; Takagi 1920 and Artin 1927 completed the classical reciprocity programme via class field theory for abelian extensions.

The applied legacy is the cryptographic infrastructure built on the efficient computability of the Legendre and Jacobi symbols. The binary Jacobi-symbol algorithm computes $(a / n)$ in $O ((lo g n)^{2})$ time using reciprocity steps — the algorithm underlying every primality-testing pre-check (Solovay-Strassen 1977, Adleman-Pomerance-Rumely 1983), every cryptographic library's Legendre-symbol computation (OpenSSL, libgmp, Crypto++), and the Tonelli-Shanks modular-square-root algorithm essential for elliptic-curve point decompression in ECDSA, EdDSA, BLS12-381. The Goldwasser-Micali probabilistic encryption scheme (1982) founded the modern provable-security paradigm with the first semantically-secure public-key encryption from the quadratic-residuosity assumption. The pattern recurs in the quadratic sieve of Pomerance 1985, the second-fastest classical integer-factorisation algorithm with sub-exponential complexity, which uses smooth values of $f (x) = x^{2} - n$ and the multiplicative structure of the Legendre symbol to build a non-degenerate congruence of squares $x^{2} \equiv y^{2} (mod n)$ from which $g cd (x - y, n)$ factors $n$ .

Full proof set Master

Proposition 1 (quadratic reciprocity, Eisenstein lattice-point proof). For distinct odd primes $p, q$ , $(p / q) (q / p) = (- 1)^{((p - 1) /2) ((q - 1) /2)}$ .

Proof. Reprised from the Key Theorem with sharpened notation. Set $P = (p - 1) /2$ , $Q = (q - 1) /2$ . We compute $(p / q) (q / p)$ by counting lattice points in the rectangle $R = {(x, y) : 1 \leq x \leq P, 1 \leq y \leq Q} \subset Z^{2}$ .

By Gauss's lemma (Proposition 4 of 21.01.06) and the parity identity $μ (q, p) \equiv \sum_{j = 1}^{P} ⌊ j q / p ⌋ (mod 2)$ (proved as Exercise 7 above), $$ \left(\frac{q}{p}\right) ;=; (-1)^{\mu(q, p)} ;=; (-1)^{\sum_j \lfloor j q / p \rfloor}. $$ Symmetrically $(p / q) = (- 1)^{\sum_{k} ⌊ k p / q ⌋}$ .

The diagonal $y = (q / p) x$ from the origin passes through no interior lattice point of $R$ : if $(x, y)$ were such a point with $y = q x / p$ , then $p y = q x$ , and $g cd (p, q) = 1$ forces $p ∣ x$ , impossible for $1 \leq x \leq P < p$ .

So every lattice point of $R$ lies strictly above or strictly below the diagonal. The number of lattice points strictly below is $$ N_{\text{below}} ;=; \sum_{x = 1}^P #{y : 1 \leq y, ; p y < q x} ;=; \sum_{x = 1}^P \lfloor q x / p \rfloor, $$ using that $⌊ q x / p ⌋ \leq Q$ for $x \leq P$ (since $q x / p \leq q (p - 1) / (2 p) < q /2 < Q + 1$ ). Symmetrically $N_{above} = \sum_{y = 1}^{Q} ⌊ p y / q ⌋$ , and $N_{below} + N_{above} = P Q$ .

Reducing modulo $2$ : $$ \sum_{x = 1}^P \lfloor q x / p \rfloor + \sum_{y = 1}^Q \lfloor p y / q \rfloor ;\equiv; P Q \pmod 2, $$ so by Gauss's lemma, $$ \left(\frac{p}{q}\right) \left(\frac{q}{p}\right) ;=; (-1)^{\sum_y \lfloor p y / q \rfloor + \sum_x \lfloor q x / p \rfloor} ;=; (-1)^{P Q} ;=; (-1)^{\frac{p - 1}{2} \cdot \frac{q - 1}{2}}. $$ $□$

Proposition 2 (Jacobi-symbol reciprocity). For $m, n$ odd coprime positive integers, $(m / n) (n / m) = (- 1)^{((m - 1) /2) ((n - 1) /2)}$ .

Proof. See Exercise 4 above. Factor $m = \prod p_{i}^{a_{i}}$ and $n = \prod q_{j}^{b_{j}}$ , expand the Jacobi symbols multiplicatively, apply quadratic reciprocity to each pair $(p_{i}, q_{j})$ , and use the identity $(N - 1) /2 \equiv \sum a_{i} (p_{i} - 1) /2 (mod 2)$ to recognise the exponent as $((m - 1) /2) ((n - 1) /2) (mod 2)$ . $□$

Proposition 3 (Jacobi-symbol supplementary laws). For $n$ odd positive integer, $(- 1/ n) = (- 1)^{(n - 1) /2}$ and $(2/ n) = (- 1)^{(n^{2} - 1) /8}$ .

Proof. See Exercise 5 above. Multiplicative expansion in the prime factorisation $n = \prod p_{i}^{a_{i}}$ , the Legendre-symbol supplementary laws for each $(\cdot / p_{i})$ , and the multiplicativity-mod- $2$ identities $(N - 1) /2 \equiv \sum a_{i} (p_{i} - 1) /2 (mod 2)$ and $(N^{2} - 1) /8 \equiv \sum a_{i} (p_{i}^{2} - 1) /8 (mod 2)$ . $□$

Proposition 4 (correctness of the binary Jacobi-symbol algorithm). The Jacobi symbol $(a / n)$ for $a, n$ positive odd coprime can be computed in $O ((lo g n)^{2})$ bit operations by the following recursive algorithm:

function jacobi(a, n):
    a = a mod n
    if a == 0:  return 0 if n != 1 else 1
    result = 1
    while a != 0:
        while a is even:
            a = a / 2
            if n mod 8 in {3, 5}:  result = -result
        swap a, n
        if a mod 4 == 3 and n mod 4 == 3:  result = -result
        a = a mod n
    return result if n == 1 else 0

Proof. Correctness follows from three operations: (i) the modular-reduction step $(a / n) = ((a mod n) / n)$ since the Jacobi symbol depends only on $a$ modulo $n$ ; (ii) the even-factor extraction $(2 a / n) = (2/ n) (a / n)$ by multiplicativity, with $(2/ n) = (- 1)^{(n^{2} - 1) /8}$ depending on $n mod 8$ ; (iii) the reciprocity flip $(a / n) \leftrightarrow (n / a)$ adjusted by the parity correction $(- 1)^{((a - 1) /2) ((n - 1) /2)}$ when both $a, n \equiv 3 (mod 4)$ . The complexity is $O ((lo g n)^{2})$ bit operations because each modular reduction halves the operand size by a factor of $2$ on average (analogous to the Euclidean algorithm), and there are $O (lo g n)$ such reductions, each costing $O (lo g n)$ bit operations. $□$

Proposition 5 (quadratic reciprocity, Gauss-sum proof). Same statement as Proposition 1, via the Gauss-sum identity $τ (χ_{p})^{2} = (- 1)^{(p - 1) /2} p$ .

Proof. See Exercise 8 above. Work in $Z [ζ_{p}]$ modulo a prime ideal above $q$ . The Frobenius at $q$ acts on the Gauss sum as $τ^{q} \equiv χ_{p} (q) τ (mod q)$ , while the algebraic identity $τ^{q} = τ (p^{*})^{(q - 1) /2}$ combined with Euler's criterion gives $τ (p^{*} / q) \equiv χ_{p} (q) τ (mod q)$ . Cancel $τ$ (unit modulo $q$ ) and use $(p^{*} / q) = (- 1)^{((p - 1) /2) ((q - 1) /2)} (p / q)$ via the first supplementary law to recover QR. $□$

Proposition 6 (quadratic reciprocity, Hilbert-symbol product-formula proof). Same statement as Proposition 1, via the Hilbert-symbol product formula $\prod_{v} (a, b)_{v} = 1$ .

Proof sketch. Apply the product formula at $a = p$ , $b = q$ for distinct odd primes $p, q$ . The Hilbert symbol $(p, q)_{v}$ takes the value $+ 1$ at every place except at $v \in {p, q, \infty}$ (and at $v = 2$ in general; for $p, q$ odd primes, $(p, q)_{2} = 1$ when $p \equiv q \equiv 1 (mod 4)$ and $- 1$ when $p \equiv q \equiv 3 (mod 4)$ — the $2$ -adic local symbol carries the supplementary-law sign).

At $v = \infty$ : $(p, q)_{\infty} = + 1$ since $p, q > 0$ (so $p X^{2} + q Y^{2}$ represents positive numbers).

At $v = p$ : $(p, q)_{p} = (q / p)$ where $q$ is a $p$ -adic unit, by the Hilbert-symbol-to-Legendre-symbol identity.

At $v = q$ : $(p, q)_{q} = (p / q)$ symmetrically.

At $v = 2$ : $(p, q)_{2} = (- 1)^{((p - 1) /2) ((q - 1) /2)}$ via local computation in $Q_{2}$ .

The product formula $\prod_{v} (p, q)_{v} = 1$ gives $(p / q) \cdot (q / p) \cdot (- 1)^{((p - 1) /2) ((q - 1) /2)} = 1$ , hence QR. $□$

Proposition 7 (decision procedure for quadratic residuosity modulo prime powers). For $p$ an odd prime, $k \geq 1$ , and $a$ coprime to $p$ : $a$ is a quadratic residue modulo $p^{k}$ iff $a$ is a quadratic residue modulo $p$ .

Proof. Direction $\Rightarrow$ : if $x^{2} \equiv a (mod p^{k})$ then $x^{2} \equiv a (mod p)$ .

Direction $\Leftarrow$ : by Hensel's lemma. Suppose $x_{0}^{2} \equiv a (mod p)$ with $p ∤ x_{0}$ . We lift inductively: given $x_{k - 1}^{2} \equiv a (mod p^{k - 1})$ , write $x_{k - 1}^{2} = a + p^{k - 1} c$ and seek $x_{k} = x_{k - 1} + p^{k - 1} t$ with $x_{k}^{2} \equiv a (mod p^{k})$ . Expanding, $$ x_k^2 ;=; x_{k - 1}^2 + 2 p^{k - 1} t x_{k - 1} + p^{2(k - 1)} t^2 ;\equiv; a + p^{k - 1}(c + 2 t x_{k - 1}) \pmod{p^k}. $$ Solve $c + 2 t x_{k - 1} \equiv 0 (mod p)$ : since $p$ is odd and $p ∤ x_{k - 1}$ (which follows from $p ∤ x_{0}$ by induction), the coefficient $2 x_{k - 1}$ is a unit modulo $p$ , so $t \equiv - c (2 x_{k - 1})^{- 1} (mod p)$ has a unique solution. Hence the lift exists, and induction completes the proof. $□$

The case $p = 2$ is more delicate: $a$ is a square modulo $2^{k}$ for $k \geq 3$ iff $a \equiv 1 (mod 8)$ .

Connections Master

Quadratic residues and the Legendre symbol 21.01.06. Just shipped. The Legendre-symbol framework of 21.01.06 supplies every operative tool used in this unit: the definition $(a / p) \in {- 1, 0, + 1}$ , Euler's criterion $a^{(p - 1) /2} \equiv (a / p) (mod p)$ , multiplicativity $(ab / p) = (a / p) (b / p)$ , the two supplementary laws $(- 1/ p) = (- 1)^{(p - 1) /2}$ and $(2/ p) = (- 1)^{(p^{2} - 1) /8}$ , and Gauss's lemma $(a / p) = (- 1)^{μ}$ . The reciprocity law of the present unit combines these with the lattice-point parity identity to compute $(p / q)$ in terms of $(q / p)$ , and the algorithmic combination computes any $(a / p)$ in $O ((lo g p)^{2})$ bit operations.
Primitive roots and structure of $(Z / n)^{\times}$ 21.01.05. Shipped. The cyclicity of $(Z / p)^{\times}$ proved in 21.01.05 supplies the existence of a primitive root $g$ modulo $p$ , which underlies Euler's criterion and the Gauss-sum proof of reciprocity: the quadratic character $χ_{p} (a) = (a / p)$ is the unique non-identity homomorphism $(Z / p)^{\times} \to {\pm 1}$ , and the Gauss sum $τ (χ_{p}) = \sum_{a} χ_{p} (a) ζ_{p}^{a}$ records the character's image in the cyclotomic field $Q (ζ_{p})$ .
Fermat-Euler-Wilson theorems 21.01.04. Shipped. The reciprocity law inherits Fermat's little theorem $a^{p - 1} \equiv 1 (mod p)$ via Euler's criterion (the Gauss-sum proof uses the Frobenius $x \mapsto x^{q}$ modulo $q$ in the cyclotomic ring $Z [ζ_{p}]$ , which is the cyclotomic-field analogue of Fermat). The first supplementary law $(- 1/ p) = + 1$ iff $p \equiv 1 (mod 4)$ characterises the primes representable as sums of two squares (Fermat 1640, Euler 1755), one of the canonical applications of 21.01.04 and one of the foundational consequences of the reciprocity-law programme.
Dedekind domains and unique factorisation of ideals 21.02.03. Pending. The Gauss-sum proof of reciprocity lives in the cyclotomic ring $Z [ζ_{p}]$ , a Dedekind domain whose ideal factorisation theory packages the Stickelberger ideal and the Frobenius-element machinery. Eisenstein's cubic and biquadratic reciprocity (1844) live in the cyclotomic rings $Z [ζ_{3}]$ and $Z [i]$ , both Euclidean domains and the simplest examples of Dedekind extensions of $Z$ . The bridge to 21.02.03 is the move from prime-number reciprocity to prime-ideal reciprocity, which is the foundational step of algebraic number theory.
Class field theory and Artin reciprocity 21.02.05. Pending. The structural generalisation of quadratic reciprocity: every finite abelian extension $L / K$ of number fields corresponds bijectively to a generalised ideal class group of $K$ , via the Artin map $p \mapsto Frob_{p}$ . Specialised to $L = Q (p^{*}) / Q$ , Artin reciprocity recovers Gauss's quadratic reciprocity. The Langlands programme is the non-abelian generalisation, conjecturally identifying Galois representations of $Gal (\overline{Q} / Q)$ with automorphic representations of reductive groups.
Cubic and biquadratic reciprocity in cyclotomic integers 21.02.06. Pending. Eisenstein 1844 proved cubic reciprocity in $Z [ζ_{3}]$ (the Eisenstein integers) and biquadratic reciprocity in $Z [i]$ (the Gaussian integers). These are the first higher-reciprocity results, generalising Gauss's quadratic reciprocity from $Z$ to cyclotomic integer rings $Z [ζ_{n}]$ , and were the bridge to Eisenstein reciprocity for $ℓ$ -th powers (Furtwängler 1909) and the general reciprocity laws of class field theory.
Galois groups and field automorphisms 01.02.04. Shipped. The Galois group $Gal (Q (ζ_{p}) / Q) ≅ (Z / p)^{\times}$ is cyclic of order $p - 1$ , and the quadratic character $χ_{p}$ corresponds via Galois theory to the unique quadratic subfield $Q (p^{*}) \subset Q (ζ_{p})$ . The Frobenius element $Frob_{q} \in Gal (Q (p^{*}) / Q)$ at a prime $q$ unramified in this extension equals $(p^{*} / q)$ — the explicit form of Artin reciprocity for the simplest abelian extension of $Q$ beyond the rationals themselves.
Cyclotomic extensions and roots of unity 01.02.05. Shipped. The cyclotomic field $Q (ζ_{p})$ — the splitting field of $x^{p} - 1$ over $Q$ — contains the Gauss sum $τ (χ_{p}) = p^{*}$ , which lives in the quadratic subfield $Q (p^{*}) \subset Q (ζ_{p})$ . The Gauss-sum proof of quadratic reciprocity (Exercise 8 above) is intrinsically a cyclotomic-field calculation: the Frobenius modulo $q$ acts on $ζ_{p}$ as $ζ_{p} \mapsto ζ_{p}^{q}$ , and tracking this action on the Gauss sum recovers reciprocity.
Dirichlet $L$ -functions and primes in arithmetic progressions 21.03.02. Pending. The Legendre symbol $a \mapsto (a / p)$ extends to the quadratic Dirichlet character $χ_{p} : (Z / p)^{\times} \to {\pm 1} \subset C^{\times}$ , and the Dirichlet $L$ -function $L (s, χ_{p}) = \sum_{n} χ_{p} (n) n^{- s}$ has functional equation and Euler product. Dirichlet 1837 proved $L (1, χ) \neq = 0$ for non-principal $χ$ to deduce the infinitude of primes in arithmetic progressions; the quadratic Dirichlet $L$ -functions are the simplest non-principal twists of $ζ (s)$ and the prototype for the entire Dirichlet $L$ -function theory. The Riemann hypothesis for $L (s, χ_{p})$ — the Generalised Riemann Hypothesis in the quadratic case — controls the error term in the prime-counting function $π (x; q, a)$ for primes in arithmetic progression $a (mod q)$ .
Hilbert symbol and adelic reciprocity 21.03.04. Pending. Hilbert 1897 packaged quadratic reciprocity and the two supplementary laws into the single adelic statement $\prod_{v} (a, b)_{v} = 1$ , where $(a, b)_{v}$ is the Hilbert symbol at each place $v$ of $Q$ . The Hilbert-symbol formulation generalises directly to number fields and is the foundation for the adelic / idelic class field theory of Chevalley 1933, Tate 1950, and the Langlands programme.

Historical & philosophical context Master

Euler 1744 Comm. Acad. Petrop. 14, 151-181 is the originator of quadratic reciprocity in the disguised form of theorems about divisors of binary quadratic forms $p a^{2} + q b^{2}$ . Euler observed empirically that the set of prime divisors of $a^{2} - q$ depends only on the residue class of the prime modulo $4 q$ — a statement equivalent to quadratic reciprocity once translated through the Legendre-symbol formalism (not available to Euler). Continued in Euler 1783 Opera Postuma I, 64-84, which contains the cleanest formulation Euler attained.

Legendre 1798 Essai sur la théorie des nombres introduced the symbol $(a / p)$ that bears his name and gave the modern formulation of the reciprocity law: for distinct odd primes $p, q$ , $(p / q) (q / p) = (- 1)^{((p - 1) /2) ((q - 1) /2)}$ . Legendre's proof is incomplete: it depends on the unproven assumption that for every residue class $a (mod m)$ coprime to $m$ , there exist infinitely many primes $p \equiv a (mod m)$ — a statement equivalent to Dirichlet's theorem on primes in arithmetic progressions, not proved until Dirichlet 1837 via the analytic non-vanishing $L (1, χ) \neq = 0$ for non-principal Dirichlet characters. So Legendre had the right statement but no complete proof.

Gauss 1801 Disquisitiones Arithmeticae arts. 125-152 ^{[Gauss 1801]} gave the first complete proof. Gauss had discovered the law independently in April 1796 (mathematical diary entry of 19 April 1796: "Per inductionem inveni 24 Mart. 1796") as a $19$ -year-old, and called it the theorema aureum — "the golden theorem" — or the fundamental theorem of arithmetic in his later writings. The 1801 Disquisitiones proof is by induction on the larger prime, with eight separate cases by the parities of $p, q$ modulo $4$ and the various splittings; article 131 is the central inductive step. Gauss produced seven more proofs over the next two decades ^{[Gauss 1808]} ^{[Gauss 1818]}, six of which appeared in Werke II 1863. Gauss's stated intent in proving the law eight times was to find the conceptually right proof — and the multiplicity of methods is itself a signal that the law sits at a deep junction of arithmetic, geometry, and analysis. Today more than $300$ independent proofs are known, catalogued in Lemmermeyer 2000 Reciprocity Laws ^{[Lemmermeyer 2000]}; Lemmermeyer's web-maintained running count now exceeds $345$ proofs.

Eisenstein 1844 J. reine angew. Math. 27 proved cubic reciprocity in the cyclotomic ring $Z [ζ_{3}]$ of Eisenstein integers, with the companion paper Crelle 28 giving biquadratic reciprocity in $Z [i]$ . These are the first higher-reciprocity results, generalising Gauss's quadratic reciprocity from $Z$ to cyclotomic integer rings $Z [ζ_{n}]$ . Eisenstein 1845 J. reine angew. Math. 28, 246-248 ^{[Eisenstein 1845]} then gave the geometric lattice-point proof of quadratic reciprocity: count integer points strictly under the line of slope $q / p$ inside the rectangle $[1, (p - 1) /2] \times [1, (q - 1) /2]$ in two ways. This is the canonical proof reproduced in every modern textbook (Hardy-Wright Ch. VI, Ireland-Rosen §5.3, Serre Ch. I §3) and the proof we present as the Key Theorem above.

Dirichlet 1854 / Dedekind 1894 gave the Gauss-sum proof of reciprocity using the evaluation $τ (χ_{p})^{2} = (- 1)^{(p - 1) /2} p$ of the quadratic Gauss sum in the cyclotomic field $Q (ζ_{p})$ . The sign determination $τ (χ_{p}) = + (- 1)^{(p - 1) /2} p$ is Gauss's 1805 result (after four years of attempts, recorded as the diary entry of 30 August 1805: "Endlich entdeckt — Heureka! num = $Δ + Δ + Δ$ " — a different Eureka moment, but the Gauss-sum sign came in 1805). Dedekind's supplements to Dirichlet's Vorlesungen introduce the modern abelian-group framework of characters, prefiguring the entire $L$ -function programme.

Jacobi 1837 J. reine angew. Math. 30, 166-182 extended the Legendre symbol to the Jacobi symbol $(a / n)$ for $n$ odd positive composite, by multiplicativity in the prime-power decomposition. The Jacobi symbol satisfies the same reciprocity law $(m / n) (n / m) = (- 1)^{((m - 1) /2) ((n - 1) /2)}$ for $m, n$ odd coprime positive, and the same two supplementary laws. The algorithmic consequence is the binary Jacobi-symbol algorithm: compute $(a / n)$ in $O ((lo g n)^{2})$ time by alternating reduction $a mod n$ and reciprocity flip, without factoring $n$ . This is the algorithm used in every modern cryptographic library.

Hilbert 1897 Jahresber. DMV 4, 175-546 ^{[Hilbert 1897]} — the Zahlbericht, Hilbert's encyclopaedic report on algebraic number theory commissioned by the DMV in 1893 — developed the Hilbert symbol $(a, b)_{v}$ at each place $v$ of a number field and the product formula $\prod_{v} (a, b)_{v} = 1$ . The Hilbert symbol at a finite prime $p$ detects whether $Z^{2} - a X^{2} - b Y^{2}$ has non-zero solutions over the local field $Q_{p}$ ; quadratic reciprocity becomes the Euler-factor matching of the product formula. Hilbert's 9th problem (1900 ICM Paris) ^{[Hilbert 1900]} asks for the most general reciprocity law in any algebraic number field — the question answered by Takagi 1920 and Artin 1927.

Furtwängler 1909 Math. Ann. 67, 1-31 ^{[Furtwängler 1909]} proved the Eisenstein reciprocity law for the $ℓ$ -th power residue symbol in $Z [ζ_{ℓ}]$ for $ℓ$ an odd prime, generalising Eisenstein's 1850 statement to all $ℓ$ . A precursor to the general reciprocity laws of class field theory.

Takagi 1920 J. Coll. Sci. Tokyo 41, 1-133 ^{[Takagi 1920]} proved class field theory for relatively abelian extensions of number fields: every finite abelian extension $L / K$ corresponds bijectively to a generalised ideal class group of $K$ , with the conductor-discriminant formula expressing the abelian $L$ -function as a product of Hecke $L$ -functions. Specialised to $K = Q$ and quadratic $L = Q (d)$ , Takagi's theorem reduces to quadratic reciprocity. Artin 1927 Hamb. Abh. 5, 353-363 ^{[Artin 1927]} added the explicit Frobenius-isomorphism formulation — the Artin reciprocity law — identifying the Artin map $I_{K} (m) / P_{L / K} (m) \sim Gal (L / K)$ as the canonical isomorphism. The non-abelian generalisation is the Langlands programme: Artin reciprocity equals abelian Langlands; the Langlands functoriality conjectures (Langlands 1967 letter to Weil; Langlands 1970 Yale Lectures) extend to all reductive groups via $L$ -functions of automorphic representations.

The applied legacy: the binary Jacobi-symbol algorithm computes Legendre symbols efficiently and underlies the Solovay-Strassen primality test (1977), the Tonelli-Shanks modular-square-root algorithm essential for elliptic-curve point decompression, and the Goldwasser-Micali 1982 first semantically-secure encryption scheme. The quadratic sieve of Pomerance 1985 — the second-fastest classical integer-factorisation algorithm, with sub-exponential complexity $L_{n} [1/2, c]$ — uses the multiplicative structure of the Legendre symbol to build a non-degenerate congruence of squares $x^{2} \equiv y^{2} (mod n)$ from which $g cd (x - y, n)$ factors $n$ . The same quadratic-residue framework Gauss developed in 1801 underlies every modern cryptographic protocol involving modular square roots.

Bibliography Master

@book{Gauss1801,
  author    = {Gauss, Carl Friedrich},
  title     = {Disquisitiones Arithmeticae},
  publisher = {Gerhard Fleischer},
  address   = {Leipzig},
  year      = {1801},
  note      = {Articles 125-152 contain the first complete proof of quadratic reciprocity (Gauss's first proof, by induction on the larger prime), completed April 1796 according to Gauss's mathematical diary. Article 151 calls the law the theorema aureum. English translation by Arthur A. Clarke, Yale University Press, 1965/1986.}
}

@article{Gauss1808,
  author  = {Gauss, Carl Friedrich},
  title   = {Theorematis arithmetici demonstratio nova},
  journal = {Commentationes Societatis Regiae Scientiarum Gottingensis},
  year    = {1808},
  note    = {Gauss's third proof of quadratic reciprocity, via Gauss's lemma and absolute-residue counting. Reprinted in Werke II (1863), 1-8. Founded the lemma-and-counting tradition continued by Eisenstein.}
}

@article{Gauss1818,
  author  = {Gauss, Carl Friedrich},
  title   = {Theorematis fundamentalis in doctrina de residuis quadraticis demonstrationes et amplificationes novae},
  journal = {Commentationes Societatis Regiae Scientiarum Gottingensis},
  year    = {1818},
  note    = {Gauss's fourth, fifth, and sixth proofs: the Gauss-sum proof via cyclotomic periods (foundational for the entire theory of Gauss sums); the cyclotomic-polynomial proof; the higher-reciprocity-style proof using $p$-th roots of unity. Werke II (1863), 47-64.}
}

@article{Eisenstein1845,
  author  = {Eisenstein, Gotthold},
  title   = {Geometrischer Beweis des Fundamentaltheorems f{\"u}r die quadratischen Reste},
  journal = {Journal f{\"u}r die reine und angewandte Mathematik},
  volume  = {28},
  pages   = {246--248},
  year    = {1845},
  note    = {The lattice-point-counting proof of quadratic reciprocity. Canonical modern textbook proof: count integer points under the line of slope $q/p$ inside the rectangle $[1, (p-1)/2] \times [1, (q-1)/2]$ in two ways.}
}

@article{Eisenstein1844,
  author  = {Eisenstein, Gotthold},
  title   = {Beweis des Reciprocit{\"a}tssatzes f{\"u}r die cubischen Reste in der Theorie der aus den dritten Wurzeln der Einheit zusammengesetzten complexen Zahlen},
  journal = {Journal f{\"u}r die reine und angewandte Mathematik},
  volume  = {27},
  pages   = {289--310},
  year    = {1844},
  note    = {Cubic reciprocity in the cyclotomic ring $\mathbb{Z}[\zeta_3]$ of Eisenstein integers. Companion paper Crelle 28 (1844), 53-67 gives biquadratic reciprocity in $\mathbb{Z}[i]$. The first higher-reciprocity results.}
}

@book{DirichletDedekind1894,
  author    = {Dirichlet, Peter Gustav Lejeune and Dedekind, Richard},
  title     = {Vorlesungen {\"u}ber Zahlentheorie},
  edition   = {4},
  publisher = {Vieweg},
  address   = {Braunschweig},
  year      = {1894},
  note      = {Sections 52-58 give Dirichlet's Gauss-sum proof of quadratic reciprocity using the evaluation $\tau(\chi_p)^2 = (-1)^{(p-1)/2} p$ of the quadratic Gauss sum. Dedekind's supplements introduce the modern abelian-group framework of characters.}
}

@article{Hilbert1897,
  author  = {Hilbert, David},
  title   = {Die Theorie der algebraischen Zahlk{\"o}rper},
  journal = {Jahresbericht der Deutschen Mathematiker-Vereinigung},
  volume  = {4},
  pages   = {175--546},
  year    = {1897},
  note    = {The Zahlbericht — Hilbert's encyclopaedic report on algebraic number theory. Develops the Hilbert symbol $(a, b)_v$ at each place of a number field and the product formula $\prod_v (a, b)_v = 1$. Quadratic reciprocity becomes Euler-factor matching of the product formula.}
}

@misc{Hilbert1900,
  author  = {Hilbert, David},
  title   = {Mathematische Probleme},
  howpublished = {Address before the International Congress of Mathematicians, Paris, 8 August 1900. G{\"o}ttinger Nachrichten 1900, 253-297; English translation Bulletin AMS 8 (1902), 437-479},
  year    = {1900},
  note    = {The 9th problem: proof of the most general reciprocity law in an arbitrary number field. Motivated class field theory; answered by Takagi 1920 and Artin 1927 for abelian extensions.}
}

@article{Takagi1920,
  author  = {Takagi, Teiji},
  title   = {{\"U}ber eine Theorie des relativ-Abelschen Zahlk{\"o}rpers},
  journal = {Journal of the College of Science, Tokyo},
  volume  = {41},
  pages   = {1--133},
  year    = {1920},
  note    = {Class field theory for relatively abelian extensions of number fields. Every finite abelian extension corresponds bijectively to a generalised ideal class group via the Artin map. Specialised to $K = \mathbb{Q}$ and quadratic $L$, reduces to quadratic reciprocity.}
}

@article{Artin1927,
  author  = {Artin, Emil},
  title   = {Beweis des allgemeinen Reziprozit{\"a}tsgesetzes},
  journal = {Abhandlungen aus dem Mathematischen Seminar der Universit{\"a}t Hamburg},
  volume  = {5},
  pages   = {353--363},
  year    = {1927},
  note    = {Artin reciprocity. The Artin map induces an isomorphism from generalised ideal classes to the Galois group, sending a prime $\mathfrak{p}$ to its Frobenius element. The modern formulation of all reciprocity laws for abelian extensions.}
}

@article{Furtwangler1909,
  author  = {Furtw{\"a}ngler, Philipp},
  title   = {Allgemeiner Existenzbeweis f{\"u}r den Klassenk{\"o}rper eines beliebigen algebraischen Zahlk{\"o}rpers},
  journal = {Mathematische Annalen},
  volume  = {67},
  pages   = {1--31},
  year    = {1909},
  note    = {Proof of the Eisenstein reciprocity law for the $\ell$-th power residue symbol in $\mathbb{Z}[\zeta_\ell]$ for $\ell$ odd prime. Precursor to general class-field-theoretic reciprocity.}
}

@book{Lemmermeyer2000,
  author    = {Lemmermeyer, Franz},
  title     = {Reciprocity Laws: From Euler to Eisenstein},
  series    = {Springer Monographs in Mathematics},
  publisher = {Springer},
  address   = {Berlin},
  year      = {2000},
  note      = {The definitive modern monograph on quadratic reciprocity and its higher generalisations. Catalogues more than $300$ independent proofs of QR (web-maintained count now exceeds $345$). Chapters 1-9 develop the historical proof tradition from Euler 1744 through Gauss's eight proofs to Eisenstein's lattice-point proof.}
}

@book{IrelandRosen1990,
  author    = {Ireland, Kenneth and Rosen, Michael},
  title     = {A Classical Introduction to Modern Number Theory},
  edition   = {2},
  series    = {Graduate Texts in Mathematics},
  volume    = {84},
  publisher = {Springer},
  year      = {1990},
  note      = {Chapter 5 §§5.2-5.3 develops quadratic reciprocity with a careful proof via Gauss's lemma and Eisenstein's lattice-point counting, plus the Jacobi-symbol generalisation. Chapter 6 develops the Gauss-sum proof. Chapter 11 develops cubic and biquadratic reciprocity.}
}

@book{Apostol1976,
  author    = {Apostol, Tom M.},
  title     = {Introduction to Analytic Number Theory},
  series    = {Undergraduate Texts in Mathematics},
  publisher = {Springer},
  year      = {1976},
  note      = {Sections 9.6-9.7 give the statement of QR, the Gauss-sum derivation, the Jacobi-symbol algorithm, and the application to deciding quadratic residuosity for arbitrary moduli.}
}

@book{Serre1973,
  author    = {Serre, Jean-Pierre},
  title     = {A Course in Arithmetic},
  series    = {Graduate Texts in Mathematics},
  volume    = {7},
  publisher = {Springer},
  year      = {1973},
  note      = {Chapter I §3 gives Serre's clean adelic-style proof of quadratic reciprocity via the Hilbert symbol and the product formula. The shortest rigorous modern treatment.}
}

@book{NivenZuckermanMontgomery1991,
  author    = {Niven, Ivan and Zuckerman, Herbert S. and Montgomery, Hugh L.},
  title     = {An Introduction to the Theory of Numbers},
  edition   = {5},
  publisher = {Wiley},
  year      = {1991},
  note      = {Sections 3.2-3.3 develop quadratic reciprocity at the undergraduate level with worked examples. Standard undergraduate textbook.}
}

@book{HardyWright2008,
  author    = {Hardy, G. H. and Wright, E. M.},
  title     = {An Introduction to the Theory of Numbers},
  edition   = {6},
  publisher = {Oxford University Press},
  year      = {2008},
  note      = {Revised by D. R. Heath-Brown and J. H. Silverman. Chapters V-VII develop quadratic residues and the Legendre symbol with two proofs of quadratic reciprocity: Gauss's lemma + Eisenstein lattice-point counting (Ch. VI §6.13) and the Gauss-sum proof (Ch. VII).}
}

@book{Cox2013,
  author    = {Cox, David A.},
  title     = {Primes of the form $x^2 + n y^2$: Fermat, class field theory, and complex multiplication},
  edition   = {2},
  publisher = {Wiley},
  year      = {2013},
  note      = {The canonical modern textbook on the consequences of quadratic reciprocity for Fermat-style primes-of-the-form problems, with the originator chain Fermat-Euler-Lagrange-Legendre-Gauss developed from primary sources.}
}

@book{Burton2010,
  author    = {Burton, David M.},
  title     = {Elementary Number Theory},
  edition   = {7},
  publisher = {McGraw-Hill},
  year      = {2010},
  note      = {Chapter 9 §9.3 develops quadratic reciprocity at the undergraduate Beginner-tier level with worked examples for small primes and a step-by-step computation of the Legendre symbol using the reciprocity flip.}
}

Prerequisites

21.01.04
21.01.05
21.01.06

Tier anchors

beginner: Burton 2010 *Elementary Number Theory* 7e §9.3 (statement of quadratic reciprocity with worked examples for small primes, the two supplementary laws restated, a step-by-step computation of $(a/p)$ using the reciprocity flip); Khan Academy 'Modular arithmetic — quadratic reciprocity' module
intermediate: Ireland-Rosen 1990 *A Classical Introduction to Modern Number Theory* (Springer GTM 84, 2e) §5.2-5.3 (statement of QR, proof via Gauss's lemma and Eisenstein's lattice-point counting, the Jacobi-symbol generalisation, applications to deciding QR); Apostol 1976 *Introduction to Analytic Number Theory* §9.6-9.7 (statement of QR, the Gauss-sum derivation, the Jacobi-symbol binary algorithm); Niven-Zuckerman-Montgomery 1991 *An Introduction to the Theory of Numbers* 5e §3.2-3.3
master: Gauss 1801 *Disquisitiones Arithmeticae* arts. 125-152 (originator: the first complete proof of quadratic reciprocity by induction, called the theorema aureum); Gauss 1808 *Theorematis arithmetici demonstratio nova* (Göttingen) (Gauss's third proof via the lemma and absolute-residue counting); Gauss 1818 *Theorematis fundamentalis in doctrina de residuis quadraticis demonstrationes et amplificationes novae* (Werke II, 47-64) (Gauss's fourth, fifth, sixth proofs — including the Gauss-sum proof); Eisenstein 1845 *J. reine angew. Math.* 28, 246-248 (Eisenstein's geometric lattice-point counting proof — the canonical modern textbook proof); Eisenstein 1844 *J. reine angew. Math.* 27, 289-310 (cubic and biquadratic reciprocity in $\mathbb{Z}[\zeta_3]$ and $\mathbb{Z}[i]$); Dirichlet 1854 (Gauss-sum proof using cyclotomic fields, expanded in Dedekind's edition of Dirichlet's *Vorlesungen* 1894); Hilbert 1897 *Jahresber. DMV* 4, 175-546 (Hilbert symbol and the product formula $\prod_v (a, b)_v = 1$); Hilbert 1900 ICM Paris (the 9th problem on general reciprocity); Takagi 1920 *J. Coll. Sci. Tokyo* 41, 1-133 (class field theory for abelian extensions of number fields); Artin 1927 *Hamb. Abh.* 5, 353-363 (Artin reciprocity, the modern formulation); Furtwängler 1909 *Math. Ann.* 67, 1-31 (Eisenstein reciprocity for the $\ell$-th power residue symbol); Lemmermeyer 2000 *Reciprocity Laws: From Euler to Eisenstein* (Springer Monographs in Mathematics) (catalogue of 300+ independent proofs); Ireland-Rosen 1990 *A Classical Introduction to Modern Number Theory* §§5-6; Serre 1973 *A Course in Arithmetic* (Springer GTM 7) Ch. I §3

References

Gauss, C. F. — Disquisitiones Arithmeticae · Leipzig: Gerhard Fleischer, 1801. Articles 125-152 contain the first complete proof of quadratic reciprocity (Gauss's first proof, by induction on the larger prime), completed April 1796 according to Gauss's mathematical diary (entry of 19 April 1796: 'Per inductionem inveni 24 Mart. 1796'). Article 131 is the central inductive step; articles 132-145 develop the eight separate cases of the induction (by the parities of $p, q$ modulo $4$ and the various splittings). Article 151 calls the law the **theorema aureum** — 'the golden theorem'. English translation by Arthur A. Clarke, Yale University Press, 1965 (1986 corrected reprint).
Gauss, C. F. — Theorematis arithmetici demonstratio nova · Commentationes Societatis Regiae Scientiarum Gottingensis, 1808. Gauss's third proof of quadratic reciprocity, via Gauss's lemma and the absolute-residue counting argument. Reprinted in Werke II (1863), 1-8. This is the proof that founded the lemma-and-counting tradition continued by Eisenstein.
Gauss, C. F. — Theorematis fundamentalis in doctrina de residuis quadraticis demonstrationes et amplificationes novae · Commentationes Societatis Regiae Scientiarum Gottingensis, 1818. Werke II (1863), 47-64. Contains Gauss's fourth, fifth, and sixth proofs: the Gauss-sum proof via cyclotomic periods (foundational for the entire theory of Gauss sums and Dirichlet $L$-functions); the cyclotomic-polynomial proof; the higher-reciprocity-style proof using the $p$-th roots of unity. Gauss's published proofs eventually numbered six; two more proofs survive in his Nachlass (Werke X).
Eisenstein, G. — Geometrischer Beweis des Fundamentaltheorems für die quadratischen Reste · *Journal für die reine und angewandte Mathematik* 28 (1845), 246-248. The lattice-point-counting proof: count integer points strictly under the line of slope $q/p$ inside the rectangle $[1, (p - 1)/2] \times [1, (q - 1)/2]$ in two ways — first by columns (giving $\sum_{j} \lfloor j q / p \rfloor$, controlling $(q/p)$ via Gauss's lemma) and second by rows (giving $\sum_{k} \lfloor k p / q \rfloor$, controlling $(p/q)$). The two sums add to $((p - 1)/2)((q - 1)/2)$, giving the reciprocity exponent. This is the canonical proof reproduced in every modern textbook (Hardy-Wright Ch. VI, Ireland-Rosen §5.3, Serre Ch. I §3).
Eisenstein, G. — Beweis des Reciprocitätssatzes für die cubischen Reste · *Journal für die reine und angewandte Mathematik* 27 (1844), 289-310. Cubic reciprocity in $\mathbb{Z}[\zeta_3]$. Companion paper Eisenstein 1844 *J. reine angew. Math.* 28, 53-67 gives biquadratic reciprocity in $\mathbb{Z}[i]$. Together these are the first higher-reciprocity results — generalising Gauss's quadratic reciprocity from the rational integers $\mathbb{Z}$ to the cyclotomic integer rings $\mathbb{Z}[\zeta_n]$, founding the algebraic-number-theory route to general reciprocity.
Dirichlet, P. G. L. — Vorlesungen über Zahlentheorie · Edited and supplemented by R. Dedekind. Braunschweig: Vieweg, 1st edition 1863, 2nd 1871, 3rd 1879, 4th 1894. §§52-58 give Dirichlet's Gauss-sum proof of quadratic reciprocity using the evaluation $\tau(\chi_p)^2 = (-1)^{(p - 1)/2} p$ of the quadratic Gauss sum $\tau(\chi_p) = \sum_{a = 1}^{p - 1} \chi_p(a) \zeta^a$ for $\zeta = e^{2\pi i / p}$. The sign determination $\tau(\chi_p) = +\sqrt{(-1)^{(p - 1)/2} p}$ is Gauss's 1805 result (after four years of attempts, recorded as the diary entry of 30 August 1805). Dedekind's supplements introduce the modern abelian-group framework of characters.
Hilbert, D. — Die Theorie der algebraischen Zahlkörper (Zahlbericht) · *Jahresbericht der Deutschen Mathematiker-Vereinigung* 4 (1897), 175-546. The *Zahlbericht* — Hilbert's encyclopaedic report on algebraic number theory commissioned by the DMV in 1893. Part IV §§64-90 develops Hilbert's general reciprocity formula via the **Hilbert symbol** $(a, b)_p \in \{\pm 1\}$ at each place $p$ of $\mathbb{Q}$, with the product formula $\prod_p (a, b)_p = 1$ over all places (finite and infinite). The Hilbert symbol at a finite place $p$ for $a, b \in \mathbb{Q}_p^\times$ records whether $a x^2 + b y^2 = z^2$ has a non-zero solution in $\mathbb{Q}_p$; quadratic reciprocity is equivalent to the product formula by Euler-factor matching.
Hilbert, D. — Mathematische Probleme · Address delivered before the International Congress of Mathematicians at Paris, 8 August 1900. *Göttinger Nachrichten* 1900, 253-297; English translation in *Bulletin AMS* 8 (1902), 437-479. The 9th problem: 'Beweis des allgemeinsten Reciprocitätsgesetzes in einem beliebigen Zahlkörper' — proof of the most general reciprocity law in an arbitrary number field. The question motivated class field theory; answered by Takagi 1920 and Artin 1927 for abelian extensions, with the non-abelian generalisation conjectured by Langlands 1967.
Takagi, T. — Über eine Theorie des relativ-Abelschen Zahlkörpers · *Journal of the College of Science, Tokyo* 41 (1920), 1-133. Takagi's class field theory: every finite abelian extension $L/K$ of a number field $K$ corresponds bijectively to a generalised ideal class group of $K$ via the Artin map; the conductor-discriminant formula expresses the abelian $L$-function as a product of Hecke $L$-functions. Specialised to $K = \mathbb{Q}$ and quadratic extensions $L = \mathbb{Q}(\sqrt{d})$, Takagi's theorem reduces to quadratic reciprocity. Takagi's monograph *Daisuteki seisuron* (Algebraic Number Theory, Iwanami, 1948) is the standard exposition.
Artin, E. — Beweis des allgemeinen Reziprozitätsgesetzes · *Hamburger Abhandlungen* 5 (1927), 353-363. Artin reciprocity: for $L/K$ finite abelian, the **Artin map** $\mathrm{Art}_{L/K} : I_K(\mathfrak{m}) / P_{L/K}(\mathfrak{m}) \to \mathrm{Gal}(L/K)$ from generalised ideal classes (modulo a conductor $\mathfrak{m}$) to the Galois group is an isomorphism. Specialised to the quadratic extension $\mathbb{Q}(\sqrt{p^*})/\mathbb{Q}$ where $p^* = (-1)^{(p - 1)/2} p$ is the signed prime, the Frobenius element at $q$ acts by $(p^*/q)$, recovering quadratic reciprocity.
Furtwängler, P. — Allgemeiner Existenzbeweis für den Klassenkörper eines beliebigen algebraischen Zahlkörpers · *Mathematische Annalen* 67 (1909), 1-31. Furtwängler's proof of the **Eisenstein reciprocity law** for the $\ell$-th power residue symbol in $\mathbb{Z}[\zeta_\ell]$ for $\ell$ an odd prime, generalising Eisenstein's 1850 statement to all $\ell$. A precursor to the general reciprocity laws of class field theory.
Lemmermeyer, F. — Reciprocity Laws: From Euler to Eisenstein · Springer Monographs in Mathematics. Berlin: Springer, 2000. The definitive modern monograph on quadratic reciprocity and its higher generalisations. Catalogues more than $300$ independent proofs of quadratic reciprocity (Lemmermeyer's website maintains the running count, now exceeding $345$ proofs). Chapters 1-9 develop the historical proof tradition from Euler 1744 through Gauss's eight proofs to Eisenstein's lattice-point proof. Chapters 10-13 develop cubic, quartic, sextic, and octic reciprocity. The standard reference for any historical or comparative work on reciprocity laws.
Ireland, K. and Rosen, M. — A Classical Introduction to Modern Number Theory · Springer Graduate Texts in Mathematics 84, 2nd edition (1990). Chapter 5 §§5.2-5.3 develops quadratic reciprocity with a careful proof via Gauss's lemma and Eisenstein's lattice-point counting, plus the Jacobi-symbol generalisation. Chapter 6 develops the Gauss-sum proof. Chapter 11 develops cubic and biquadratic reciprocity in cyclotomic integer rings. The standard graduate-text reference.
Apostol, T. M. — Introduction to Analytic Number Theory · Springer Undergraduate Texts in Mathematics, 1976. §§9.6-9.7 give the statement of QR, the Gauss-sum derivation, the Jacobi-symbol algorithm, and the application to deciding quadratic residuosity for arbitrary moduli. Apostol's exposition is the gold standard for the analytic perspective on QR.
Serre, J.-P. — A Course in Arithmetic · Springer Graduate Texts in Mathematics 7, 1973. Chapter I §3 gives Serre's clean adelic-style proof of quadratic reciprocity via the Hilbert symbol and the product formula. The shortest rigorous modern treatment, building the Hilbert-symbol calculus directly without intermediate technicalities.
Niven, I., Zuckerman, H. S., and Montgomery, H. L. — An Introduction to the Theory of Numbers · Wiley, 5th edition (1991). §§3.2-3.3 develop quadratic reciprocity at the undergraduate level with worked examples. The standard undergraduate textbook from which much of the canonical exposition descends.
Hardy, G. H. and Wright, E. M. — An Introduction to the Theory of Numbers · Oxford University Press, 6th edition (2008), revised by D. R. Heath-Brown and J. H. Silverman. Chapters V-VII develop quadratic residues and the Legendre symbol, with two proofs of quadratic reciprocity: Gauss's lemma + Eisenstein lattice-point counting (Ch. VI §6.13) and the Gauss-sum proof (Ch. VII). Chapter VI §6.10 gives the historical timeline.
Cox, D. A. — Primes of the form $x^2 + n y^2$ · Wiley, 2nd edition (2013). Chapter 1 develops Fermat's two-square theorem and its descendants via quadratic reciprocity; Chapter 4 is the class-field-theoretic interpretation through the Hilbert class field; Chapter 5 connects to ring class fields and complex multiplication. The canonical modern textbook on the consequences of QR for 'primes of the form' problems.

Estimated time

beginner: 22m
intermediate: 55m
master: 95m