Fact-checked by Grok 2 weeks ago

Quadratic reciprocity

In number theory, the law of quadratic reciprocity is a fundamental theorem that provides a criterion for determining whether an odd prime p is a quadratic residue modulo another distinct odd prime q, and vice versa, via the Legendre symbol \left( \frac{p}{q} \right), which equals 1 if p is a quadratic residue modulo q (and not divisible by q), -1 if it is a nonresidue, and 0 if q divides p. The precise statement, for distinct odd primes p and q, is \left( \frac{p}{q} \right) \left( \frac{q}{p} \right) = (-1)^{\frac{p-1}{2} \cdot \frac{q-1}{2}}, supplemented by formulas for the symbols involving -1 and 2: \left( \frac{-1}{p} \right) = (-1)^{\frac{p-1}{2}} and \left( \frac{2}{p} \right) = (-1)^{\frac{p^2-1}{8}}. The theorem was first formulated by Leonhard Euler around 1783, with providing early statements and incomplete proofs in 1785 and 1798, including the introduction of the in his work Essai sur la Théorie des Nombres. delivered the first complete proof in 1801 at age 24 in his seminal , later providing at least eight distinct proofs himself, including one using Gauss sums that influenced . offered a geometric reproof in the mid-19th century using lattice points, simplifying aspects of Gauss's earlier arguments, though he died young in 1852. Dubbed the "golden theorem" by Gauss for its profound insight, quadratic reciprocity enables the characterization of primes representable in quadratic forms like x^2 + n y^2 for small n (e.g., n = 1, 2, 3), exactly half of the nonzero residues modulo an odd prime being quadratic residues. Its enduring significance lies in bridging elementary and , inspiring higher reciprocity laws such as cubic and biquadratic versions, and finding modern applications in , including the Rabin cryptosystem. Over 300 proofs exist as of 2014, reflecting its central role in the field.

Introduction and Motivation

Historical Context and Early Observations

The study of quadratic residues modulo primes dates back to the , when explored conditions under which primes can be expressed as sums of two squares, a problem connected to quadratic residuosity—for an odd prime p, p = x^2 + y^2 if and only if -1 is a p (i.e., p \equiv 1 \pmod{4}). Fermat's investigations into such representations involved computing quadratic residues but did not extend to general reciprocity between distinct primes. Building on these ideas in the mid-18th century, Leonhard Euler made more systematic observations about reciprocity in quadratic residuosity between distinct odd primes p and q. Around 1744, Euler conjectured that the residuosity of p q is often the same as that of q p, specifically that \left( \frac{p}{q} \right) = \left( \frac{q}{p} \right) when at least one of p or q is congruent to 1 4, and \left( \frac{p}{q} \right) = -\left( \frac{q}{p} \right) when both are congruent to 3 4; he verified this through extensive computations but lacked a general proof. These patterns emerged from Euler's investigations into quadratic forms and prime representations, including early checks of specific cases like whether 2 is a 7 (yes, as $3^2 \equiv 2 \pmod{7}) and 5 (no, as the nonzero squares 5 are 1 and 4). These 17th- and 18th-century efforts laid the groundwork for later developments in the theory of quadratic reciprocity, culminating in Adrien-Marie Legendre's partial formulations in the 1780s and Carl Friedrich Gauss's complete proof in 1801.

Examples of Quadratic Patterns

One motivation for studying quadratic reciprocity arises from the connection between quadratic residues and the in quadratic extensions of . Consider the expression n^2 - 5, which factors as (n - \sqrt{5})(n + \sqrt{5}) over the reals but remains irreducible over the integers. In the ring \mathbb{Z}[\sqrt{5}], the norm of an element n + m\sqrt{5} is n^2 - 5m^2, and for a prime p not dividing 5, the prime ideal generated by p factors if and only if 5 is a quadratic residue modulo p, meaning the congruence x^2 \equiv 5 \pmod{p} has a solution. This illustrates how the quadratic residuosity of 5 modulo p determines whether p remains prime or splits in the \mathbb{Q}(\sqrt{5}). Computing residues modulo small primes reveals intriguing patterns that vary systematically but are not immediately predictable without reciprocity laws. The residues modulo a prime p are the possible values of x^2 \pmod{p} for x = 0, 1, \dots, p-1, excluding multiples of p for nonzero residues. For instance:
Prime p residues modulo p (nonzero)
31
51, 4
71, 2, 4
111, 3, 4, 5, 9
131, 3, 4, 9, 10, 12
These lists show that exactly (p-1)/2 nonzero residues exist for each odd prime p, but determining membership for a specific a requires checking squares or using advanced tools. Early observations of such patterns in residue tables were noted by Fermat and Euler in their investigations of congruences. A striking asymmetry appears when comparing the quadratic residuosity of two distinct odd primes p and q both congruent to 3 modulo 4. In these cases, the Legendre symbol \left( \frac{p}{q} \right) frequently equals the negative of \left( \frac{q}{p} \right), indicating that naive reciprocity \left( \frac{p}{q} \right) = \left( \frac{q}{p} \right) does not hold universally. For example, take p = 7 and q = 11: the squares modulo 11 are 0, 1, 3, 4, 5, 9, so 7 is not among them and \left( \frac{7}{11} \right) = -1; meanwhile, \left( \frac{11}{7} \right) = \left( \frac{4}{7} \right) = 1 since $4 = 2^2. This reversal highlights the need for adjustments based on the primes' residues modulo 4. Legendre, in his early formulation of reciprocity, encountered cases where direct equality failed without accounting for such supplements, as in the above example where \left( \frac{11}{7} \right) = 1 but \left( \frac{7}{11} \right) = -1. These discrepancies in anecdotal computations, such as differing residuosity directions for pairs like and (where \left( \frac{3}{7} \right) = -1 while \left( \frac{7}{3} \right) = 1), underscored the necessity for refined supplementary rules to unify the patterns.

Fundamentals of Quadratic Residues

Definition and Basic Properties

In , for an odd prime p and an a coprime to p (i.e., \gcd(a, p) = 1), a is called a p if there exists an x such that x^2 \equiv a \pmod{p}. If no such x exists, then a is a quadratic non-residue p. Note that 0 is trivially a quadratic residue p since $0^2 \equiv 0 \pmod{p}, but the focus here is on nonzero residues. Among the p-1 nonzero residues p, exactly (p-1)/2 are residues, and the remaining (p-1)/2 are quadratic non-residues. This follows from the fact that the squaring map x \mapsto x^2 \pmod{p} on the \mathbb{Z}_p^\times is a 2-to-1 onto the of quadratic residues, with each nonzero residue having exactly two square (namely, x and -x). The set of quadratic residues forms a of index 2 in \mathbb{Z}_p^\times. The quadratic residues are closed under multiplication: if a and b are quadratic residues modulo p, then so is ab \pmod{p}, since if x^2 \equiv a \pmod{p} and y^2 \equiv b \pmod{p}, it follows that (xy)^2 \equiv ab \pmod{p}. More generally, the product of two non-residues is a residue, while the product of a residue and a non-residue is a non-residue. A key property distinguishing residues from non-residues is given by Euler's criterion: for an odd prime p and a coprime to p, a is a p a^{(p-1)/2} \equiv 1 \pmod{p}, and a quadratic non-residue a^{(p-1)/2} \equiv -1 \pmod{p}. For example, consider p = 5. The squares 5 are $1^2 \equiv 1, $2^2 \equiv 4, $3^2 \equiv 4, and $4^2 \equiv 1, so the residues are 1 and 4, while 2 and 3 are non-residues.

The Legendre Symbol

The Legendre symbol is a mathematical that encodes residuosity an odd prime, serving as a multiplicative on the of that prime. For an a and an odd prime p, the \left( \frac{a}{p} \right) is defined as 1 if a is a p (meaning there exists an x such that x^2 \equiv a \pmod{p} and p \nmid a), -1 if a is a quadratic nonresidue p (no such x exists), and 0 if p divides a. This symbol exhibits several fundamental properties that facilitate its use in number theory. It is completely multiplicative in the numerator: for any integers a and b, \left( \frac{ab}{p} \right) = \left( \frac{a}{p} \right) \left( \frac{b}{p} \right), provided p is an odd prime. Additionally, \left( \frac{a}{p} \right) = \left( \frac{b}{p} \right) if a \equiv b \pmod{p}, and \left( \frac{p}{p} \right) = 0 since p divides p. It is defined for odd primes, where it acts as a non-trivial character of order 2. Basic computations of the Legendre symbol leverage its properties, particularly for powers of integers. For instance, if a is not divisible by p, then \left( \frac{a^2}{p} \right) = 1, as a^2 is always a p under this condition; more generally, \left( \frac{a^k}{p} \right) = \left( \frac{a}{p} \right)^k follows from multiplicativity. One standard method to evaluate \left( \frac{a}{p} \right) for p \nmid a is Euler's criterion: a^{(p-1)/2} \equiv \left( \frac{a}{p} \right) \pmod{p}, which directly links the symbol to . Examples illustrate these properties effectively. Consider p = 5: the quadratic residues modulo 5 are 0, , and 4, so \left( \frac{[1](/page/1)}{5} \right) = 1, \left( \frac{4}{5} \right) = 1 (since $2^2 \equiv 4 \pmod{5}), and \left( \frac{3}{5} \right) = -1 (no solution to x^2 \equiv 3 \pmod{5}); using Euler's criterion, $3^{(5-1)/2} = 3^2 = 9 \equiv 4 \equiv -1 \pmod{5}, confirming the value. For p = 7, \left( \frac{3}{7} \right) = -1, as $3^{(7-1)/2} = 3^3 = 27 \equiv -1 \pmod{7}, indicating 3 is a nonresidue modulo 7. These computations highlight the symbol's role in distinguishing residues without exhaustive square checks.

The Quadratic Reciprocity Theorem

Main Statement

The law of quadratic reciprocity relates the Legendre symbols \left( \frac{p}{q} \right) and \left( \frac{q}{p} \right) for distinct odd primes p and q. It states that \left( \frac{p}{q} \right) \left( \frac{q}{p} \right) = (-1)^{\frac{(p-1)(q-1)}{4}}. This product equals -1 if and only if both p \equiv 3 \pmod{4} and q \equiv 3 \pmod{4}; in that case, \left( \frac{p}{q} \right) = -\left( \frac{q}{p} \right). Otherwise, the symbols are equal: \left( \frac{p}{q} \right) = \left( \frac{q}{p} \right). For instance, with p=5 and q=13, both congruent to $1 \pmod{4}, the symbols are equal. Reducing gives \left( \frac{13}{5} \right) = \left( \frac{3}{5} \right), and further computation yields \left( \frac{3}{5} \right) = -1, so \left( \frac{5}{13} \right) = -1. As another example, take p=3 and q=7, both congruent to $3 \pmod{4}. Then \left( \frac{3}{7} \right) = -\left( \frac{7}{3} \right) = -\left( \frac{1}{3} \right) = -1, confirming that $3 is a quadratic nonresidue modulo $7. The facilitates determining quadratic residuosity by reducing the to progressively smaller primes until direct evaluation is possible.

Supplementary Laws

The supplementary laws of quadratic reciprocity address the cases where the fixed integer q is -1 or $2, providing explicit criteria for the \left( \frac{q}{p} \right) in terms of the residue class of an odd prime p $4 or $8. These laws, first rigorously established by in his (1801), complete the framework needed to evaluate quadratic residuosity for small q when combined with the main reciprocity for odd primes. The first supplementary law determines whether -1 is a modulo p: \left( \frac{-1}{p} \right) = (-1)^{(p-1)/2}. This equals $1 if p \equiv 1 \pmod{4} and -1 if p \equiv 3 \pmod{4}. Thus, -1 is a modulo p if and only if p = 2 or p \equiv 1 \pmod{4}. The second supplementary law handles the case of $2: \left( \frac{2}{p} \right) = (-1)^{(p^2-1)/8}. This equals $1 if p \equiv \pm 1 \pmod{8} (i.e., p \equiv 1 or $7 \pmod{8}) and -1 if p \equiv \pm 3 \pmod{8} (i.e., p \equiv 3 or $5 \pmod{8}). Consequently, $2 is a quadratic residue modulo p if and only if p = 2 or p \equiv \pm 1 \pmod{8}. For q = \pm 3 and q = \pm 5, the main reciprocity law yields explicit evaluations by relating \left( \frac{q}{p} \right) to \left( \frac{p}{|q|} \right) with an adjustment factor that depends on the quadratic character of q modulo $4. Since $3 \equiv 3 \pmod{4}, the adjustment introduces a sign flip: \left( \frac{3}{p} \right) = \left( \frac{p}{3} \right) (-1)^{(p-1)/2}, where \left( \frac{p}{3} \right) = 1 if p \equiv 1 \pmod{3} and -1 if p \equiv 2 \pmod{3}. Combining these, \left( \frac{3}{p} \right) = 1 if and only if p \equiv 1 or $11 \pmod{12}. For negative values, \left( \frac{-3}{p} \right) = \left( \frac{-1}{p} \right) \left( \frac{3}{p} \right), so -3 is a quadratic residue modulo p if and only if p \equiv 1 \pmod{3}. Since $5 \equiv 1 \pmod{4}, there is no sign adjustment: \left( \frac{5}{p} \right) = \left( \frac{p}{5} \right), where \left( \frac{p}{5} \right) = 1 if p \equiv 1 or $4 \pmod{5} and -1 if p \equiv 2 or $3 \pmod{5}. Thus, $5 is a p if and only if p \equiv \pm 1 \pmod{5}. For -5, \left( \frac{-5}{p} \right) = \left( \frac{-1}{p} \right) \left( \frac{5}{p} \right), so -5 is a p if and only if p \equiv 1 \pmod{4} and p \equiv \pm 1 \pmod{5}, or p \equiv 3 \pmod{4} and p \equiv \pm 2 \pmod{5}. For higher odd primes q, the pattern follows from the main law: if q \equiv 1 \pmod{4}, then \left( \frac{q}{p} \right) = \left( \frac{p}{q} \right); if q \equiv 3 \pmod{4}, then \left( \frac{q}{p} \right) = \left( \frac{p}{q} \right) (-1)^{(p-1)/2}. For example, since $7 \equiv 3 \pmod{4}, \left( \frac{7}{p} \right) = \left( \frac{p}{7} \right) (-1)^{(p-1)/2}, where \left( \frac{p}{7} \right) depends on p \pmod{7}. These relations, derived directly from the core theorem, enable recursive computation of the Legendre symbol for any fixed prime q.

Proofs of the Theorem

Proofs of the Supplementary Laws

The supplementary laws for the law of quadratic reciprocity concern the values of the Legendre symbol \left( \frac{-1}{p} \right) and \left( \frac{2}{p} \right) for an odd prime p. These can be proved elementarily using Gauss's lemma, which relates the to a count of certain residues. Gauss's lemma states that if p is an odd prime and a is an not divisible by p, then \left( \frac{a}{p} \right) = (-1)^\mu, where \mu is the number of integers k = 1, 2, \dots, (p-1)/2 for which the least positive residue of a k \pmod{p} exceeds p/2. To prove the first supplementary law, consider \left( \frac{-1}{p} \right). The multiples are (-1) \cdot k \pmod{p} for k = 1 to (p-1)/2. The least positive residue of -k \pmod{p} is p - k. Since $1 \leq k \leq (p-1)/2, it follows that p/2 < p - k \leq p - 1 < p. Thus, all (p-1)/2 residues exceed p/2, so \mu = (p-1)/2. Therefore, \left( \frac{-1}{p} \right) = (-1)^{(p-1)/2}, which equals $1 if p \equiv 1 \pmod{4} and -1 if p \equiv 3 \pmod{4}. For the second supplementary law, consider \left( \frac{2}{p} \right). The multiples are $2k \pmod{p} for k = 1 to (p-1)/2. Since $2k \leq p-1 < p, the least positive residue is $2k. This residue exceeds p/2 precisely when k > p/4. The value of \mu is thus the number of integers k from $1 to (p-1)/2 satisfying k > p/4, which equals (p-1)/2 - \lfloor p/4 \rfloor. Computing this modulo $2 yields \mu \equiv (p^2 - 1)/8 \pmod{2}. Therefore, \left( \frac{2}{p} \right) = (-1)^{(p^2 - 1)/8}, which equals $1 if p \equiv 1 or $7 \pmod{8} and -1 if p \equiv 3 or $5 \pmod{8}. To verify, consider cases: for p = 8m + 1, \lfloor p/4 \rfloor = 2m, \mu = 4m - 2m = 2m (even); for p = 8m + 3, \mu = (4m + 1) - 2m = 2m + 1 (odd); for p = 8m + 5, \mu = (4m + 2) - (2m + 1) = 2m + 1 (odd); for p = 8m + 7, \mu = (4m + 3) - (2m + 1) = 2m + 2 (even). For the law involving -3, an elementary derivation independent of the main reciprocity theorem uses quadratic Gauss sums. The quadratic Gauss sum is G = \sum_{k=0}^{p-1} \left( \frac{k}{p} \right) e^{2\pi i k / p}, and its evaluation gives G^2 = (-1)^{(p-1)/2} p. Extending to the character for the ring \mathbb{Z}[\omega] where \omega is a primitive cube root of unity leads to \left( \frac{-3}{p} \right) = 1 if p \equiv 1 \pmod{3} and -1 if p \equiv 2 \pmod{3}. Alternatively, assuming the main theorem, \left( \frac{-3}{p} \right) = \left( \frac{p}{3} \right), since the exponent (p-1)/2 terms cancel. Higher cases like \left( \frac{5}{p} \right) can be derived directly from the main reciprocity law. Specifically, \left( \frac{5}{p} \right) = \left( \frac{p}{5} \right) for odd prime p \neq 5, since (5-1)/2 = 2 is even. Thus, \left( \frac{5}{p} \right) = 1 if p \equiv \pm 1 \pmod{5} and -1 if p \equiv \pm 2 \pmod{5}. For example, if p = 7 \equiv 2 \pmod{5}, then \left( \frac{5}{7} \right) = -1; direct check shows no solution to x^2 \equiv 5 \pmod{7}.

Proofs of the Main Theorem

The first complete proof of the main quadratic reciprocity theorem was given by in 1796, utilizing on the larger of the two distinct odd primes p and q, assuming p < q. The approach begins by considering an identity derived from the geometry of numbers or continued fractions, specifically finding integers e, r, and f such that e^2 = p r + q f, where e is even, $0 < r < q, and f is odd with $0 < f < q. Reducing this equation modulo p relates the Legendre symbol (q/p) to (f/p), and by the induction hypothesis applied to the smaller primes p and f, (f/p) = (-1)^{(p-1)(f-1)/4} (p/f). Further reductions modulo f and r then connect back to (p/q), ultimately yielding (q/p) = (-1)^{(p-1)(q-1)/4} (p/q). This inductive step establishes the theorem for all such primes, marking a significant achievement in elementary number theory. A key tool in several subsequent proofs, including Gauss's own later developments, is Gauss's , which provides an explicit criterion for evaluating the Legendre symbol. For an odd prime p and integer a coprime to p, let n be the number of integers k = 1, 2, \dots, (p-1)/2 such that the least positive residue of a k \mod p exceeds p/2 (equivalently, the fractional part \{a k / p\} > 1/2). Then, \left( \frac{a}{p} \right) = (-1)^n. This lemma allows direct computation of the symbol by counting these "negative" residues and is foundational for proofs that avoid full . One influential proof employing Gauss's lemma is Gauss's third proof from 1808, later simplified by in 1845 into a more intuitive geometric form using finite lattice point counting. To prove (p/q)(q/p) = (-1)^{(p-1)/2 \cdot (q-1)/2}, apply Gauss's lemma to both symbols: for (q/p), n_p counts the k from 1 to (p-1)/2 with q k \mod p > p/2; similarly, n_q for (p/q). The product of the symbols is then (-1)^{n_p + n_q}. The key insight is that n_p + n_q \equiv (p-1)(q-1)/4 \pmod{2}, established by considering the lattice points (x, y) with x = 1, \dots, (p-1)/2 and y = 1, \dots, (q-1)/2. The total number of such points is ((p-1)/2) \cdot ((q-1)/2), and double-counting those lying strictly below the line y = (q/p) x (or equivalently, above y = (p/q) x in a symmetric view) shows that the discrepancy in crossings—corresponding to n_p and n_q—differs by exactly (p-1)(q-1)/4 modulo 2, confirming the exponent. This finite geometric argument avoids infinite processes and highlights the theorem's combinatorial depth. Eisenstein also offered an alternative proof using trigonometric identities and infinite series expansions of sine functions, leading to evaluations involving complex numbers and Gauss sums, but the lattice point method remains the preferred finite variant for its accessibility. In a modern classical sketch, the theorem follows from properties of the (\mathbb{Z}/p\mathbb{Z})^*, which is cyclic of order p-1; the of quadratic residues has index 2, and the reciprocity arises from comparing the orders of elements in the groups modulo p and q, though full details invoke character sums akin to Dirichlet's L-functions for non-vanishing at s=1. However, these build on the elementary foundations above. To illustrate the application within such a proof, consider p=5 and q=13. First, compute (13/5) = (3/5) since $13 \equiv 3 \pmod{5}. For Gauss's lemma with a=3, p=5: the values are $3 \cdot 1 \mod 5 = 3 > 2.5 and $3 \cdot 2 \mod 5 = 1 < 2.5, so n=1 and (3/5) = (-1)^1 = -1. Now for (5/13): k=1 to $6, the residues are 5, 10, 2, 7, 12, 4; those >6.5 are 10, 7, 12 (k=2,4,5), so n=3 and (5/13) = (-1)^3 = -1. Thus, (5/13)(13/5) = (-1)(-1) = 1, matching (-1)^{(5-1)/2 \cdot (13-1)/2} = (-1)^{2 \cdot 6} = 1, verifying the theorem via the .

Historical Development

Contributions from Fermat and Euler

laid foundational groundwork for quadratic reciprocity through his investigations into quadratic residues and sums of two squares in the 1640s. In a letter to dated December 25, 1640, Fermat claimed without proof that every odd prime congruent to 1 modulo 4 can be expressed as a sum of two squares, which implicitly relied on a partial reciprocity relation for such primes. He employed the method of infinite descent to derive related results, such as characterizing primes representable as sums of two squares. For instance, this connection illustrates the symmetry observed in quadratic characters for such primes, like \left( \frac{[13](/page/13)}{5} \right) = \left( \frac{5}{[13](/page/13)} \right) = 1. Leonhard Euler significantly expanded on Fermat's ideas around 1783, formulating the complete statement of quadratic reciprocity for distinct odd primes p and q in unpublished manuscripts and letters. Euler asserted that \left( \frac{p}{q} \right) \left( \frac{q}{p} \right) = (-1)^{\frac{p-1}{2} \cdot \frac{q-1}{2}}, meaning the symbols are equal if at least one prime is congruent to 1 modulo 4 and opposite if both are congruent to 3 modulo 4. He rigorously proved the supplementary laws: \left( \frac{-1}{p} \right) = (-1)^{\frac{p-1}{2}} and \left( \frac{2}{p} \right) = (-1)^{\frac{p^2-1}{8}}, employing techniques including continued fractions for evaluating quadratic characters and on prime sizes. To support his , Euler compiled a table of examples for numerous prime pairs, verifying the reciprocity pattern—for instance, equality when both primes are 1 modulo 4 (e.g., \left( \frac{5}{[13](/page/13)} \right) = \left( \frac{[13](/page/13)}{5} \right) = 1) and negation when both are 3 modulo 4 (e.g., \left( \frac{[3](/page/3)}{7} \right) = -\left( \frac{7}{[3](/page/3)} \right)). Despite these advances, Euler's proof of the main remained incomplete, depending heavily on inductive patterns derived from computations involving more than 50 primes rather than a general argument, and his work was not published at the time.

Legendre's Formulation and Symbol

In 1785, Adrien-Marie Legendre published the first complete statement of the quadratic reciprocity theorem in his memoir Recherches d'analyse indéterminée, integrating the main reciprocity law for distinct odd primes with supplementary laws for the cases involving -1 and 2. He attempted to prove the theorem using the method of , a technique inspired by earlier work in Diophantine equations, but the argument contained significant gaps, particularly in handling certain cases of prime congruences. These deficiencies were later rectified by in his rigorous proofs beginning in 1796. Building on partial results conjectured by Leonhard Euler in unpublished manuscripts, Legendre's 1785 formulation marked the first published synthesis of the full theorem, though Euler's contributions had anticipated elements of the law for specific prime pairs. In 1798, Legendre introduced the \left( \frac{a}{p} \right) in his work Essai sur la Théorie des Nombres as a concise notation to indicate whether an integer a is a an odd prime p: it equals 1 if a is a nonzero quadratic residue p, -1 if a nonzero quadratic nonresidue, and 0 if p divides a. He enumerated key properties of the symbol, including its multiplicativity—\left( \frac{ab}{p} \right) = \left( \frac{a}{p} \right) \left( \frac{b}{p} \right)—and its complete multiplicativity in the top argument when p is fixed. Legendre's version of the theorem comprised the primary reciprocity relation for distinct odd primes p and q: \left( \frac{p}{q} \right) \left( \frac{q}{p} \right) = (-1)^{\frac{p-1}{2} \cdot \frac{q-1}{2}}, along with three supplementary laws: one for -1, \left( \frac{-1}{p} \right) = (-1)^{\frac{p-1}{2}}; one for 2, \left( \frac{2}{p} \right) = (-1)^{\frac{p^2 - 1}{8}}; and a combined form for -2, \left( \frac{-2}{p} \right) = (-1)^{\frac{p^2 - 1}{8} + \frac{p-1}{2}}. These supplements allowed computation for composite arguments reducible to primes. To illustrate, Legendre demonstrated the full evaluation of \left( \frac{41}{61} \right): since 41 and 61 are distinct odd primes both congruent to 1 modulo 4, the exponent \frac{40}{2} \cdot \frac{60}{2} = 1200 is even, so \left( \frac{41}{61} \right) = \left( \frac{61}{41} \right); reducing 61 modulo 41 gives 20, and \left( \frac{20}{41} \right) = \left( \frac{4 \cdot 5}{41} \right) = \left( \frac{5}{41} \right) as \left( \frac{4}{41} \right) = 1; then \left( \frac{5}{41} \right) = \left( \frac{41}{5} \right) = \left( \frac{1}{5} \right) = 1 since 41 ≡ 1 mod 5 and the exponent \frac{4}{2} \cdot \frac{40}{2} = 80 is even, yielding \left( \frac{41}{61} \right) = 1. Historically, Legendre's efforts sparked over , as Euler had privately communicated similar ideas to contemporaries without full , leading some to question whether Legendre independently derived or adapted Euler's insights; however, Legendre's explicit statement and symbolization established his role in formalizing the for wider dissemination. Despite the proof's flaws, his 1785-1798 advancements provided the foundational framework that Gauss would perfect, influencing the development of modern .

Advanced Formulations and Generalizations

Gauss's Proofs and Alternative Statements

established quadratic reciprocity through rigorous proofs in his (1801), providing the first complete treatment of the theorem after earlier conjectural work by Euler and Legendre. In this foundational text, Gauss presented two proofs of the main theorem for distinct odd primes p and q, employing distinct methods: for the first, the theory of binary quadratic forms for the second. These proofs not only confirmed the reciprocity relation but also unified it with the supplementary laws for (-1/p) and (2/p), treating them within a cohesive framework. The first proof relies on , reducing the general case to eight base cases classified by the residues of p and q 8, with exhaustive verification of each via direct computation of residues. Detailed in Articles 125–146, this approach demonstrates the theorem's validity by assuming it holds for smaller primes and extending upward, though it is laborious and lacks deeper insight into the underlying structure. The second proof, in Article 262, draws on the composition of binary forms, showing that the reciprocity follows from the equivalence of forms representing primes p and q in each other's rings of integers. This method highlights arithmetic connections to form classes, emphasizing the theorem's role in the broader theory of forms. In 1808, Gauss published a third proof introducing his , which equates the Legendre symbol (a/p) to (-1)^n, where n counts the integers k from 1 to (p-1)/2 such that the least positive residue of a k \mod p exceeds p/2. Applying this alongside Euler's criterion yields the through a argument on residue counts. Although arithmetical, this proof inspired a geometric variant by Eisenstein (1844), interpreting the count as lattice points with even or odd coordinates in the bounded by vertices at (0,0), (1,0), and (0,1), scaled by p and q, where the total points relate to (p-1)(q-1)/4. For the supplementary laws, Gauss integrated proofs using analogous reductions: (-1/p) = (-1)^{(p-1)/2} via of permutations, and (2/p) = (-1)^{(p^2-1)/8} through similar residue analysis, all unified under the and frameworks. An alternative arithmetic statement of the main theorem is its product form: \left( \frac{p}{q} \right) \left( \frac{q}{p} \right) = (-1)^{\frac{(p-1)(q-1)}{4}}, which directly encodes the sign flip when both primes are congruent to 3 4. These proofs marked a pivotal moment in , earning the Gauss's designation as the "golden " and inspiring over 240 published proofs as of 2024, while laying groundwork for algebraic extensions.

The Jacobi Symbol

The Jacobi symbol, introduced by Carl Gustav Jacob Jacobi in 1837 as a generalization of the Legendre symbol, extends the latter to composite moduli while preserving key reciprocity properties. For an a and an odd positive n > 0 with prime factorization n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k} where each p_i is an odd prime, the \left( \frac{a}{n} \right) is defined as \left( \frac{a}{n} \right) = \prod_{i=1}^k \left( \frac{a}{p_i} \right)^{e_i}, where \left( \frac{a}{p_i} \right) denotes the . If \gcd(a, n) > 1, then \left( \frac{a}{n} \right) = 0; otherwise, it takes values in \{ -1, 1 \}. When n is prime, the coincides with the . The is completely multiplicative in both its upper and lower arguments: for odd positive integers m and n, \left( \frac{ab}{n} \right) = \left( \frac{a}{n} \right) \left( \frac{b}{n} \right) and \left( \frac{a}{mn} \right) = \left( \frac{a}{m} \right) \left( \frac{a}{n} \right). It also satisfies a analogous to quadratic reciprocity: if \gcd(a, n) = 1, then \left( \frac{a}{n} \right) = \left( \frac{n}{a} \right) (-1)^{\frac{(a-1)(n-1)}{4}}. This property allows efficient computation of the symbol via a algorithm-like procedure, reducing the problem size iteratively without requiring full factorization of n. Unlike the , the does not indicate quadratic residuosity composite n: \left( \frac{a}{n} \right) = 1 and \gcd(a, n) = 1 do not imply that a is a n, though \left( \frac{a}{n} \right) = -1 does imply it is not. For example, \left( \frac{2}{15} \right) = \left( \frac{2}{3} \right) \left( \frac{2}{5} \right) = (-1)(-1) = 1, but the quadratic residues 15 are 0, 1, 4, 6, 9, and 10, excluding 2. These properties make the Jacobi symbol valuable for simplifying computations in , particularly in algorithms requiring rapid evaluation of quadratic characters without factoring large numbers, such as certain primality tests and factorization methods.

Connections to Algebraic Number Theory

Cyclotomic Fields

The law of quadratic reciprocity finds a profound in the of cyclotomic fields, where the splitting behavior of primes in the extension \mathbb{Q}(\zeta_p)/\mathbb{Q}, with \zeta_p a primitive p-th and p an odd prime, is governed by the Frobenius automorphism. For an odd prime q \neq p, the prime ideal (q) splits completely in \mathbb{Q}(\zeta_p) q \equiv 1 \pmod{p}, but more relevantly, the Frobenius element \sigma_q \in \mathrm{Gal}(\mathbb{Q}(\zeta_p)/\mathbb{Q}) \cong (\mathbb{Z}/p\mathbb{Z})^\times has order dividing (p-1)/2 (q/p) = 1, where ( \cdot /p ) denotes the Legendre symbol; this condition implies that q splits in the unique quadratic subfield of \mathbb{Q}(\zeta_p). This connection arises from a mild form of Artin reciprocity, which equates the action of the Frobenius to the residue class of q modulo p, thereby linking the quadratic residuosity to the decomposition group. The unique quadratic subfield of \mathbb{Q}(\zeta_p) is \mathbb{Q}(\sqrt{(-1)^{(p-1)/2} p}), fixed by the subgroup of squares in (\mathbb{Z}/p\mathbb{Z})^\times, and quadratic reciprocity precisely determines the splitting of primes in this extension: an odd prime q \neq p splits completely if (q/p) = 1, remains inert if (q/p) = -1, and ramifies only at q = p. The prime p itself ramifies in \mathbb{Q}(\zeta_p) as (p) = (\lambda)^{p-1} where \lambda = 1 - \zeta_p, and this ramification descends to the quadratic subfield, where the discriminant is (-1)^{(p-1)/2} p, confirming that reciprocity encodes the ramification behavior through the supplementary laws. This framework provides an algebraic number-theoretic proof of quadratic reciprocity by comparing the Frobenius actions in the cyclotomic extension to those in quadratic fields. Furthermore, quadratic reciprocity connects to Gauss's for the imaginary \mathbb{Q}(\sqrt{-p}) (when p \equiv 3 \pmod{4}), where the class number h(-p) is given by h(-p) = \frac{1}{\pi} \sqrt{p} \, L(1, \chi_{-p}), with \chi_{-p}(n) = (-p/n) = (-1/n)(p/n) the non-principal modulo p; here, L(1, \chi_{-p}) = \sum_{n=1}^\infty \chi_{-p}(n)/n evaluates to a sum involving quadratic residues modulo p, specifically approximable by \frac{\pi}{ \sqrt{p} } \sum_{r=1}^{(p-1)/2} \chi_{-p}(r), thus linking the class number directly to the distribution of residues determined by reciprocity. This relation underscores how reciprocity facilitates computations of class numbers by providing the values of the in the . As an illustrative example, consider p=5: the cyclotomic field \mathbb{Q}(\zeta_5) has degree 4 over \mathbb{Q}, with unique quadratic subfield \mathbb{Q}(\sqrt{5}) (since $5 \equiv 1 \pmod{4}), and an odd prime q \neq 5 splits completely in \mathbb{Q}(\sqrt{5}) if and only if (5/q) = 1, which by reciprocity holds when q \equiv \pm 1 \pmod{5}; consequently, for such q, the Frobenius has order dividing 2, leading to splitting in \mathbb{Q}(\zeta_5) into either four prime ideals of degree 1 (if q \equiv 1 \pmod{5}) or two prime ideals of degree 2 (if q \equiv -1 \pmod{5}). The prime 5 ramifies as (5) = (1 - \zeta_5)^4 in the ring of integers \mathbb{Z}[\zeta_5].

Extensions to Other Rings

Quadratic reciprocity extends naturally to the ring of Gaussian integers \mathbb{Z}, where i = \sqrt{-1}, which is the ring of integers of the imaginary quadratic field \mathbb{Q}(i). The Gaussian integers form a Euclidean domain with N(a + bi) = a^2 + b^2. Primes in \mathbb{Z} are either associates of rational primes congruent to 3 modulo 4, or lie above rational primes congruent to 1 modulo 4 (which split), or the prime $1+i above 2 (which ramifies, since $2 = -(1+i)^2 / i up to units). The quadratic residue symbol ( \alpha / \pi ) for \alpha \in \mathbb{Z} and odd prime \pi \in \mathbb{Z} with \pi \nmid \alpha is defined as 1 if \alpha is a square modulo \pi, and -1 otherwise; it satisfies (\alpha / \pi) \equiv \alpha^{(N(\pi)-1)/2} \pmod{\pi}. Dirichlet proved that quadratic reciprocity holds in \mathbb{Z}: for distinct odd Gaussian primes \pi = a + bi and \rho = c + di with N(\pi) \equiv N(\rho) \equiv 1 \pmod{4}, (\pi / \rho) = (\rho / \pi). Supplementary laws include (i / \pi) = (-1)^{(N(\pi)-1)/4} and (1+i / \pi) = (-1)^{(a+b)^2/8}. A similar extension applies to the \mathbb{Z}[\omega], where \omega = e^{2\pi i / 3} is a of unity, forming the of \mathbb{Q}(\sqrt{-3}). The is N(a + b\omega) = a^2 - ab + b^2, and primes in \mathbb{Z}[\omega] lie above rational primes p \equiv 2 \pmod{3} (inert, up to units), p \equiv 1 \pmod{3} (split into two primes), or the ramified prime $1 - \omega above 3. The symbol (\alpha / \pi) for \alpha \in \mathbb{Z}[\omega] and prime \pi with N(\pi) odd is defined analogously, indicating whether \alpha is a square modulo \pi. Eisenstein's quadratic reciprocity law generalizes to this setting: for primary elements \alpha, \beta \in \mathcal{O}_K (the ) with odd norms and coprime, (\alpha / \beta) = (\beta / \alpha), where primary means congruent to a rational integer modulo (2 + \sqrt{-3}) and totally positive in the real embeddings (though imaginary fields have no real embeddings, the condition adapts to the complex structure). This reciprocity aids in determining the splitting of primes above rational primes via the Legendre symbol in \mathbb{Z}, as p \equiv 1 \pmod{3} if and only if -3 is a modulo p. In broader imaginary quadratic fields K = \mathbb{Q}(\sqrt{-d}) with d > 0 square-free, Hecke developed a reciprocity law for quadratic Hecke characters, generalizing the residue symbol to ideals. For a prime ideal \mathfrak{p} of odd norm in \mathcal{O}_K and \alpha \in K^\times coprime to \mathfrak{p}, the symbol (\alpha / \mathfrak{p}) equals \alpha^{(N\mathfrak{p} - 1)/2} \pmod{\mathfrak{p}} and indicates the quadratic residuosity in \mathcal{O}_K / \mathfrak{p}. Hecke's theorem states that for odd coprime ideals \mathfrak{a}, \mathfrak{b} generated by primary elements with appropriate congruence conditions modulo the conductor, (\mathfrak{a} / \mathfrak{b}) (\mathfrak{b} / \mathfrak{a}) = \chi(\mathfrak{b}) \chi^{-1}(\mathfrak{a}), where \chi is a quadratic Hecke character associated to the field (trivial on units and factoring through the ), incorporating infinite places via signs. This relates directly to prime splitting: a rational prime p splits in K if and only if ( -d / p ) = 1, extending classical reciprocity to ideal class behavior and Gauss sums in K. An analogous reciprocity law holds for polynomials over finite fields, modeling number-theoretic reciprocity in function field arithmetic. In F_q[T] with q odd, for distinct monic irreducible polynomials f, g \in F_q[T] of positive degree, the Legendre symbol (f / g) is 1 if f is a square in the residue field F_q[T] / (g) \cong F_{q^{\deg g}}, and -1 otherwise. The quadratic reciprocity law states (f / g) (g / f) = (-1)^{(q-1)/2 \cdot \deg f \cdot \deg g}, allowing computation of residuosity for factoring quadratics like x^2 - a \pmod{p(T)} (where p(T) is irreducible) by reciprocity with the "prime" p(T). This was first stated by Dedekind and proved by Artin, highlighting irreducibility criteria akin to prime splitting.

Higher Reciprocity Laws

Cubic and Biquadratic Reciprocity

The law of cubic reciprocity extends the quadratic reciprocity law to determine whether an integer is a cubic residue modulo a prime, particularly within the ring of Eisenstein integers \mathbb{Z}[\omega], where \omega = e^{2\pi i / 3} is a primitive cube root of unity. Carl Friedrich Gauss explored cubic residues in his Disquisitiones Arithmeticae (1801) and attempted generalizations of quadratic reciprocity, but he provided only partial results without a complete proof. The full law was established by Gotthold Eisenstein in 1844, using the arithmetic of \mathbb{Z}[\omega], which is a Euclidean domain with norm N(a + b\omega) = a^2 - ab + b^2. In \mathbb{Z}[\omega], the cubic residue symbol \left( \frac{\alpha}{\pi} \right)_3 for a prime element \pi with N(\pi) \neq 3 and \pi \nmid \alpha is defined as \alpha^{(N(\pi)-1)/3} \equiv \left( \frac{\alpha}{\pi} \right)_3 \pmod{\pi}, taking values in \{1, \omega, \omega^2\}. Eisenstein's cubic reciprocity states that for distinct primary prime elements \pi_1, \pi_2 \in \mathbb{Z}[\omega] (primary meaning \pi \equiv 2 \pmod{3}) with N(\pi_1) \neq 3, N(\pi_2) \neq 3, the symbols satisfy \left( \frac{\pi_1}{\pi_2} \right)_3 = \left( \frac{\pi_2}{\pi_1} \right)_3. For rational odd primes p, q \equiv 2 \pmod{3} (which remain prime and primary in \mathbb{Z}[\omega]), this simplifies to \left( \frac{p}{q} \right)_3 = \left( \frac{q}{p} \right)_3. A representative example is computing \left( \frac{7}{13} \right)_3, where both 7 and 13 are primes congruent to 1 modulo 3 and thus split in \mathbb{Z}[\omega] as products of primary and secondary primes. Factor 7 = (1 - 2\omega)(1 - 2\omega^2) (up to units, with $1 - 2\omega primary) and 13 = (4 + 3\omega)(4 + 3\omega^2) (up to units, with $4 + 3\omega primary); the symbol is then \left( \frac{1 - 2\omega}{4 + 3\omega} \right)_3, which by cubic reciprocity equals \left( \frac{4 + 3\omega}{1 - 2\omega} \right)_3, and further evaluation using properties of the symbol yields \omega. This reciprocity simplifies such computations compared to direct checking of cubes modulo the prime. Biquadratic reciprocity, also proved by Eisenstein in 1844, addresses quartic residues in the Gaussian integers \mathbb{Z}, building on Gauss's introduction of this ring for studying biquadratic forms, though Gauss's work on the reciprocity itself remained incomplete. For distinct Gaussian primes \pi, \sigma (with norm N(\alpha + \beta i) = \alpha^2 + \beta^2), the biquadratic residue symbol \left( \frac{\alpha}{\pi} \right)_4 takes values in the fourth roots of unity \{1, i, -1, -i\}, defined via solvability of x^4 \equiv \alpha \pmod{\pi}. The law states \left( \frac{\pi}{\sigma} \right)_4 \left( \frac{\sigma}{\pi} \right)_4 = (-1)^{\left\lfloor (N(\pi)-1)/4 \right\rfloor \left\lfloor (N(\sigma)-1)/4 \right\rfloor}. For rational primes p, q \equiv 1 \pmod{4} (which split in \mathbb{Z}), selecting primary factors (congruent to 1 modulo $2 + 2i) allows application of this relation to determine quartic residuosity.

Generalizations to Higher Powers

The generalizations of quadratic reciprocity to higher powers focus on determining whether an a is an n-th power residue modulo a \mathfrak{p} in a K containing the n-th roots of unity, for n > 2. The n-th power residue \left( \frac{a}{\mathfrak{p}} \right)_n is defined as a^{(N(\mathfrak{p})-1)/n} \mod \mathfrak{p}, taking values in the n-th roots of unity, provided N(\mathfrak{p}) \equiv 1 \mod [n](/page/N+). Early attempts at reciprocity laws for such symbols, such as for primes p \equiv 1 \mod n in \mathbb{Q}(\zeta_n), posited relations like \left( \frac{a}{p} \right)_n = \left( \frac{p}{a} \right)_n^{\tau} for some exponent \tau, but these remained incomplete without a full theoretical framework. In finite fields \mathbb{F}_q where q \equiv 1 \mod n, higher power residue symbols are constructed using multiplicative characters of order dividing n, allowing the symbol to detect n-th power residues via character sums. The general n-th power reciprocity law states that if a, b \in K^\times are coprime to each other and to n, then \left( \frac{a}{b} \right)_n \left( \frac{b}{a} \right)_n^{-1} = \prod_{p \mid n, \infty} (a, b)_p, where (a, b)_p is the Hilbert symbol at place p. This law, proved using properties of Gauss sums and cyclotomic units, extends to arbitrary number fields and marks a culmination of 19th-century efforts by Eisenstein and others on specific cases like cubic and quartic reciprocity. Emil Artin's reciprocity law of 1927 provides the modern foundation, positing that for an abelian extension L/K of number fields, the Artin map \phi_K: I_K \to \mathrm{Gal}(L/K) (from the idele group to the ) identifies unramified primes with Frobenius elements, generalizing all prior reciprocity laws including those for higher powers. Artin's theorem, central to , shows that abelian extensions are precisely those classified by ray class groups, with quadratic reciprocity as a special case via genus theory in quadratic fields. Cubic reciprocity serves as a specific instance of this framework in . The full resolution came through abelian in the , linking power residue symbols to Hecke characters of finite order. An example is quartic reciprocity in biquadratic fields like \mathbb{Q}(i), where for odd primes p, q \equiv 1 \mod 4, the symbol \left( \frac{p}{q} \right)_4 = \left( \frac{q}{p} \right)_4, adjusted by supplementary laws involving units like $1+i; this determines splitting in \mathbb{Q}(\sqrt{p}, \sqrt{q}) and follows from Eisenstein's work extended by class field theory.