Quadratic reciprocity

In number theory, the law of quadratic reciprocity is a theorem about modular arithmetic that gives conditions for the solvability of quadratic equations modulo prime numbers. Due to its subtlety, it has many formulations, but the most standard statement is:

This law, together with its supplements, allows the easy calculation of any Legendre symbol, making it possible to determine whether there is an integer solution for any quadratic equation of the form $x^{2}\equiv a{\bmod {p}}$ for an odd prime $p$ ; that is, to determine the "perfect squares" modulo $p$ . However, this is a non-constructive result: it gives no help at all for finding a specific solution; for this, other methods are required. For example, in the case $p\equiv 3{\bmod {4}}$ using Euler's criterion one can give an explicit formula for the "square roots" modulo $p$ of a quadratic residue $a$ , namely,

indeed,

This formula only works if it is known in advance that $a$ is a quadratic residue, which can be checked using the law of quadratic reciprocity.

The quadratic reciprocity theorem was conjectured by Euler and Legendre and first proved by Gauss,^[1] who referred to it as the "fundamental theorem" in his Disquisitiones Arithmeticae and his papers, writing

Privately, Gauss referred to it as the "golden theorem".^[2] He published six proofs for it, and two more were found in his posthumous papers. There are now over 240 published proofs.^[3] The shortest known proof is included below, together with short proofs of the law's supplements (the Legendre symbols of −1 and 2).

Generalizing the reciprocity law to higher powers has been a leading problem in mathematics, and has been crucial to the development of much of the machinery of modern algebra, number theory, and algebraic geometry, culminating in Artin reciprocity, class field theory, and the Langlands program.

There are an equal number of quadratic residues and non-residues; and

The product of two quadratic residues is a residue, the product of a residue and a non-residue is a non-residue, and the product of two non-residues is a residue.

Statement of the theorem[edit]

Quadratic Reciprocity (Gauss's statement). If $q\equiv 1{\bmod {4}}$ , then the congruence $x^{2}\equiv p{\bmod {q}}$ is solvable if and only if $x^{2}\equiv q{\bmod {p}}$ is solvable. If $q\equiv 3{\bmod {4}}$ and $p\equiv 3{\bmod {4}}$ , then the congruence $x^{2}\equiv p{\bmod {q}}$ is solvable if and only if $x^{2}\equiv -q{\bmod {p}}$ is solvable.

Quadratic Reciprocity (combined statement). Define $q^{*}=(-1)^{\frac {q-1}{2}}q$ . Then the congruence $x^{2}\equiv p{\bmod {q}}$ is solvable if and only if $x^{2}\equiv q^{*}{\bmod {p}}$ is solvable.

Quadratic Reciprocity (Legendre's statement). If p or q are congruent to 1 modulo 4, then: $x^{2}\equiv q{\bmod {p}}$ is solvable if and only if $x^{2}\equiv p{\bmod {q}}$ is solvable. If p and q are congruent to 3 modulo 4, then: $x^{2}\equiv q{\bmod {p}}$ is solvable if and only if $x^{2}\equiv p{\bmod {q}}$ is not solvable.

The last is immediately equivalent to the modern form stated in the introduction above. It is a simple exercise to prove that Legendre's and Gauss's statements are equivalent – it requires no more than the first supplement and the facts about multiplying residues and nonresidues.

Dedekind zeta function

Rational reciprocity law

Zolotarev's lemma

(1986). Disquisitiones Arithemeticae. Translated by Clarke, Arthur A. (Second, corrected ed.). New York: Springer. ISBN 0-387-96254-9.

Gauss, Carl Friedrich

(1965). Untersuchungen über höhere Arithmetik (Disquisitiones Arithemeticae & other papers on number theory). Translated by Maser, Hermann (Second ed.). New York: Chelsea. ISBN 0-8284-0191-8.

Gauss, Carl Friedrich

The Disquisitiones Arithmeticae has been translated (from Latin) into English and German. The German edition includes all of Gauss's papers on number theory: all the proofs of quadratic reciprocity, the determination of the sign of the Gauss sum, the investigations into biquadratic reciprocity, and unpublished notes. Footnotes referencing the Disquisitiones Arithmeticae are of the form "Gauss, DA, Art. n".

The two monographs Gauss published on biquadratic reciprocity have consecutively numbered sections: the first contains §§ 1–23 and the second §§ 24–76. Footnotes referencing these are of the form "Gauss, BQ, § n".

These are in Gauss's Werke, Vol II, pp. 65–92 and 93–148. German translations are in pp. 511–533 and 534–586 of Untersuchungen über höhere Arithmetik.

Every textbook on elementary number theory (and quite a few on algebraic number theory) has a proof of quadratic reciprocity. Two are especially noteworthy:

Franz Lemmermeyer's Reciprocity Laws: From Euler to Eisenstein has many proofs (some in exercises) of both quadratic and higher-power reciprocity laws and a discussion of their history. Its immense bibliography includes literature citations for 196 different published proofs for the quadratic reciprocity law.

Kenneth Ireland and Michael Rosen's A Classical Introduction to Modern Number Theory also has many proofs of quadratic reciprocity (and many exercises), and covers the cubic and biquadratic cases as well. Exercise 13.26 (p. 202) says it all

, Encyclopedia of Mathematics, EMS Press, 2001 [1994]

"Quadratic reciprocity law"

from MathWorld

Quadratic Reciprocity Theorem

A play comparing two proofs of the quadratic reciprocity law

at PlanetMath

A proof of this theorem

at MathPages

A different proof

(332 proofs)

Quadratic reciprocity

Statement of the theorem[edit]

Dedekind zeta function

Rational reciprocity law

Zolotarev's lemma

Gauss, Carl Friedrich

Gauss, Carl Friedrich

"Quadratic reciprocity law"

Quadratic Reciprocity Theorem

A play comparing two proofs of the quadratic reciprocity law

A proof of this theorem

A different proof

F. Lemmermeyer's chronology and bibliography of proofs of the Quadratic Reciprocity Law