Quadratic reciprocity is a theorem in number theory describing a symmetry, with a precisely determined sign correction, between two questions: whether an odd prime is a square modulo another odd prime , and whether is a square modulo . Its central assertion is that the answers agree unless both primes are congruent to modulo , in which case they are opposite. Together with two supplementary laws concerning and , it provides a systematic method for deciding whether a quadratic congruence has a solution.
The theorem emerged from eighteenth-century investigations of squares and prime numbers and received its first complete proof from Carl Friedrich Gauss in 1796. Its significance extends beyond the calculation of square residues: it connects elementary modular arithmetic with quadratic fields, character sums, and local–global principles. The search for analogous laws for higher powers became one of the principal motivations for modern algebraic number theory.
Quadratic residues and the Legendre symbol
Let be an odd prime and let be an integer not divisible by . The integer is a quadratic residue modulo if there is an integer satisfying
Otherwise it is a quadratic nonresidue. The terminology depends only on the residue class of : adding a multiple of does not change the question. For example, the nonzero squares modulo are , since the squares of are congruent to , and the remaining nonzero inputs give the same values.
The Legendre symbol records this distinction:
Despite its appearance, this notation is not a fraction. Its lower argument is an odd prime, while its upper argument may be any integer. In particular, depends on , not on the numerical size or sign of .
The residue classes modulo form a finite field . Its nonzero elements form a multiplicative group, and the squaring map on this group has kernel . Consequently exactly nonzero residue classes are squares. Their products and inverses are again squares, so they form a subgroup of index . This group-theoretic structure explains the multiplicative identity
Thus the product of two nonresidues is a residue, although neither factor is itself a square.
Euler’s criterion gives an equivalent computational description:
when . Indeed, Fermat’s little theorem implies that this power is a root of , so it is or . Every nonzero square gives ; a root-counting argument for a polynomial shows that no additional inputs can do so.
Euler’s criterion tests a particular numerator against a particular prime. Quadratic reciprocity adds something qualitatively different: it relates two tests with the numerator and denominator interchanged. That relationship permits repeated reductions to smaller numbers and reveals that the apparent irregularity of square residues is governed by a simple rule.
The reciprocity law and its supplements
For distinct odd primes and , quadratic reciprocity states
The exponent is odd precisely when both and are congruent to . Equivalently,
The restriction to distinct primes excludes a trivial zero case: if , both symbols vanish and the displayed sign formula does not apply.
The first supplementary law determines the status of :
Thus is a square modulo exactly when . For example, , whereas no square is congruent to . This supplement also determines the effect of replacing a numerator by its negative.
The second supplementary law handles the even prime:
The exponent is an integer for every odd . In terms of residue classes,
For instance, is a square modulo , since , but it is not a square modulo .
Small examples illustrate the essential sign distinction. The primes and are both . Here is a square modulo , since , but is not a square modulo . By contrast, , so
Indeed, .
A frequent consequence is a classification of primes for which a fixed small integer is a square. Applying reciprocity to , and excluding , gives
Similarly,
for odd primes . The first classification requires both a reciprocity sign and reduction modulo ; the second has no sign correction because .
Historical development
Problems about the representation of primes by quadratic expressions supplied much of the background to quadratic reciprocity. Pierre de Fermat studied assertions such as the representation of primes congruent to as sums of two squares. Such results naturally lead to questions about when , , or another fixed integer is a square modulo a prime divisor of a quadratic expression. Before reciprocity was formulated as a single theorem, many of its individual consequences appeared as separate patterns.
Leonhard Euler investigated these patterns extensively during the eighteenth century. He recognized relationships between the prime divisors of quadratic forms and the congruence classes of the primes involved, and formulated versions of the reciprocity phenomenon. The modern symbolic expression, however, should not be projected unchanged onto these early investigations: their language was often that of divisors of forms rather than a uniform calculus of residue symbols.
Adrien-Marie Legendre gave an explicit formulation in a memoir published in 1785 and developed the subject further in his Essai sur la théorie des nombres of 1798. The notation now called the Legendre symbol made the statement especially compact. His attempted proofs did not establish the theorem in full generality; they relied on assertions about the existence of primes with specified residue properties that had not been proved in the required generality.
Gauss found a complete proof in 1796, at the age of eighteen, and published it in Disquisitiones Arithmeticae in 1801. His treatment made reciprocity a central organizing theorem of arithmetic rather than an isolated observation. The proof used a carefully structured induction with auxiliary results about quadratic residues. Gauss subsequently returned to the theorem repeatedly and produced several proofs based on different ideas, including methods associated with products of residues and roots of unity.
The multiplication of proofs was mathematically productive. A result whose elementary statement concealed several different structures could be approached through counting, permutations, cyclotomic expressions, and quadratic forms. During the nineteenth century, these approaches helped identify the concepts needed for reciprocity laws in broader settings. Gauss’s work on biquadratic residues, for example, led naturally to arithmetic involving complex integers rather than ordinary integers alone.
The historical importance of quadratic reciprocity therefore lies both in its resolution and in the problems it generated. The effort to generalize it contributed to the development of algebraic integers, ideals, and field extensions. Later reciprocity theories preserved its basic theme—connecting residue information at different primes—while replacing the elementary sign rule with more general algebraic structures.
An elementary proof through Gauss’s lemma
One of the most transparent proofs combines Gauss’s lemma for quadratic residues with a lattice-point count. Let be an odd prime, coprime to , and . Consider
and reduce each term to its least positive residue modulo . Let count how many of these residues exceed . Gauss’s lemma asserts
To see why, replace every residue above by its negative modulo , producing integers between and . Their absolute values are distinct: an equality would imply , which forces within the given range. They therefore constitute a permutation of . Multiplying gives
Cancellation and Euler’s criterion prove the lemma.
For odd positive , the same lemma yields the useful parity formula
Here is the greatest integer not exceeding . To verify the parity relation, write , with , and let be the absolute least residue. Modulo , replacing by changes the sum by one for each of the replacements, because is odd. Since the permute and is odd, summing the equations gives .
Now take distinct odd primes , and put
In the rectangle of integer points
no point lies on the line . Such an equality would force , which is impossible in this range. For each , the number of points with is . Similarly, summing counts the points on the other side. Hence
Applying the parity formula to the two sums proves reciprocity.
The supplements fit the same framework. For , all residues lie above . For , the relevant count is
Its parity, evaluated for , gives the supplementary law for . Thus a single residue-counting principle proves all three laws.
Computation, Jacobi symbols, and quadratic equations
Quadratic reciprocity turns residue testing into a reduction procedure resembling the Euclidean algorithm. First reduce the numerator modulo the denominator. Remove factors of using the second supplement, then interchange odd numerator and denominator, introducing a minus sign only when both are . Repetition eventually reaches a numerator of , or detects a common factor.
For a direct example,
No negative sign appears in the first interchange because . A further application gives
Thus is a square modulo , without searching through the possible roots.
For efficient general computation, the Jacobi symbol extends the notation to every positive odd denominator. If
define
with value when . Its multiplicativity, reciprocity law, and supplementary laws allow its evaluation without first factoring . In particular, for positive odd coprime ,
An iterative algorithm therefore needs only remainders, removal of powers of , swaps, and sign changes.
The distinction between Legendre and Jacobi symbols is essential. A Jacobi value of need not indicate an actual square modulo a composite denominator. For example,
but has no solution because it already has none modulo . This distinction underlies the Solovay–Strassen primality test, which checks the prime-modulus identity relating Euler’s criterion to a Jacobi symbol; composite integers can fail that identity.
Residue testing also decides the solvability of a general quadratic equation modulo an odd prime. If , then
is equivalent to
The discriminant therefore determines whether there are zero, one, or two roots. Reciprocity decides whether a nonzero discriminant is a square; it does not itself construct its square root. Algorithms such as the Tonelli–Shanks algorithm perform that separate task. For composite moduli, prime-power analysis and the Chinese remainder theorem replace the single prime-field calculation.
Quadratic fields and representation by forms
A central algebraic interpretation concerns the splitting of primes in a quadratic number field
where is squarefree. This is a degree-two extension of the rational numbers. Its ring of algebraic integers is
The field discriminant is correspondingly or .
For an odd prime , the prime ideal factorization of has two possibilities. If , then
with two distinct prime ideals, each having residue field ; the prime is said to split. If , then remains prime, and its residue field has elements; the prime is inert. Primes dividing ramify instead. Thus a question about the congruence becomes a statement about prime factorization in another number system.
The Kronecker symbol, an extension of the Jacobi symbol that also handles even denominators, packages the splitting information as
For a quadratic field discriminant , this is a real Dirichlet character of modulus . Quadratic reciprocity explains why the behavior of varying primes in a fixed quadratic field can be expressed by congruence classes modulo a fixed integer. For , for example, odd primes other than split precisely when they are or .
The connection with quadratic forms is related but more refined. A binary form
has discriminant . If an odd prime is represented by the form, reduction modulo gives
For a prime representation, cannot vanish modulo under these assumptions, so the discriminant must be a square modulo .
Such a residue condition is not generally sufficient for representation by a specified form: distinct equivalence classes of forms can share a discriminant. In the special case of , however, the splitting condition in does give the familiar theorem that an odd prime is a sum of two integer squares exactly when it is . For more general discriminants, the distinction between splitting and representation records additional ideal-class information that quadratic reciprocity alone does not determine.
Character sums and analytic interpretations
For an odd prime , the function
is multiplicative on the nonzero residue classes and takes values in . Extending it by makes it convenient for finite sums. This character viewpoint connects reciprocity with harmonic analysis on finite groups: additive oscillations and multiplicative residue information can be combined in a single expression.
The basic quadratic Gauss sum is
Its coefficients are arithmetic signs, while its exponential factors are roots of unity in the complex numbers. A fundamental identity is
In particular, , with real for and purely imaginary for . The identity follows by combining the absolute-value calculation with
These sums also explain how quadratic characters behave under a finite Fourier transform. If , a change of variable gives
Thus the transformed character is a scalar multiple of itself. The nontrivial square-root factor in this identity is an analytic manifestation of the same sign structure that occurs in elementary reciprocity.
Reciprocity can be derived by comparing Gauss sums associated with different primes inside fields generated by roots of unity. The comparison requires more than the squared identity alone: it must track how automorphisms act on the roots of unity and therefore on the sums. This approach places the elementary theorem within Galois theory, where a residue symbol describes the action of an arithmetic automorphism on an algebraic quantity.
Quadratic characters also define Dirichlet -functions,
Their Euler products organize primes according to the splitting values , , and . Reciprocity supplies the fixed-modulus character that makes this analytic treatment possible. Through Dirichlet’s theorem on primes in arithmetic progressions, splitting and inert primes in a quadratic field each have density among all primes, after the finitely many ramified primes are excluded. Reciprocity itself does not prove that distribution theorem; it identifies the congruence classes to which the theorem applies.
Local–global formulations and higher reciprocity
A symmetric formulation of quadratic reciprocity uses completions of the rational numbers. These include the real field and the fields of -adic numbers , one for each prime . For nonzero rational , the Hilbert symbol at a place is if
has a nonzero solution over the corresponding completion, and is otherwise. It records a local solvability condition for a quadratic form.
Hilbert reciprocity states
Only finitely many factors differ from . For distinct odd primes , the nontrivial contributions for can occur only at and ; the real contribution is because both numbers are positive. More explicitly,
while
The product formula therefore gives exactly the classical reciprocity law. In this language, its apparently exceptional sign is the contribution from the prime .
This formulation is related to, but distinct from, the Hasse–Minkowski theorem, which states that a quadratic form over the rationals has a nontrivial rational zero if and only if it has one over the reals and over every . The product formula constrains the collection of local symbols; the Hasse–Minkowski theorem turns a complete set of local solvability conditions into a global rational solution. Both express the special effectiveness of local methods for quadratic equations.
For higher powers, the analogous questions become more intricate. Cubic and quartic reciprocity laws concern third- and fourth-power residues. Their natural settings involve rings containing the corresponding roots of unity, rather than only ordinary integers. Cubic reciprocity is naturally expressed using Eisenstein integers, while quartic reciprocity uses Gaussian integers. Choices of suitable prime generators and congruence normalizations replace the simple distinction between primes congruent to or .
The broad abelian generalization is class field theory. Its Artin reciprocity law relates ideal-theoretic arithmetic in a number field to the automorphism groups of its abelian extensions. For a quadratic extension of the rationals, the automorphism group has two elements, and the Frobenius automorphism of an unramified prime is encoded by the quadratic character . Classical quadratic reciprocity is therefore the degree-two instance of a framework in which residue symbols describe how primes act in field extensions. Extensions with nonabelian automorphism groups require structures beyond the abelian reciprocity map.