- Quadratic reciprocity
The law of quadratic reciprocity is a theorem from
modular arithmetic, a branch of number theory, which shows a remarkable relationship between the solvability of certain quadratic equations modulo different prime moduli.
Although it allows us to determine whether any quadratic equation modulo a prime number has a solution, it does not provide any help at all for actually "solving" it. (The article
quadratic residuediscusses algorithms for this.)
The theorem was conjectured by Euler and Legendre and first proven by Gauss. [Gauss, DA § 4, arts 107-150] He refers to it as the 'fundamental theorem' in the "
Disquisitiones Arithmeticae" and his papers; privately he referred to it as the 'golden theorem'. [E.g. in his mathematical diary entry for April 8, 1796(the date he first proved quadratic reciprocity). See [http://books.google.com/books?id=NM36hgqmOLkC&pg=PA30&lpg=PA30&dq=+%22theorema+aureum%22++diary+gauss&source=web&ots=m5uXIuw73w&sig=Bzhx36Y3ZVh6WniMjT6kWUIpZqY&hl=en facsilile page from Felix Klein's "Development of Mathematics in the 19th Century"] ] He was so fond of it that he provided eight separate proofs over his lifetime. There are over 200 [See F. Lemmermeyer's chronology and bibliography of proofs in the external references] published proofs.
The first section of this article does not use the Legendre symbol and states quadratic reciprocity in the two versions found by Legendre and Gauss. Statements of quadratic reciprocity using the Legendre and Jacobi symbols begin here and there are links to the formulas in the Contents. In this article "p" and "q" always refer to distinct positive odd prime numbers.
Terminology, data, and two statements of the theorem
A quadratic residue (mod "n") is any number congruent to a square (mod "n"). A quadratic nonresidue (mod "n") is any number which is not congruent to a square (mod "n"). The adjective "quadratic" can be dropped if the context makes it clear that it is implied. When working modulo primes (as in this article), it is usual to treat zero as a special case. By doing so, the following statements become true:
Modulo a prime, there are an equal number of quadratic residues and nonresidues.
Modulo a prime, the product of two quadratic residues is a residue, the product of a residue and a nonresidue is a nonresidue, and the product of two nonresidues is a residue.
Table of quadratic residues
He says that since expressions of the form will come up so often, he will abbreviate it (where it is understood gcd("N", "c") = 1):
This is now known as the
Legendre symbol, and an equivalent [The equivalence is Euler's criterion] [The analogue of Legendre's original definition is used for higher-power residue symbols] definition is used today: for all integers "a" and all odd primes "p"
Legendre's version of quadratic reciprocity
He notes that these can be combined::
A number of proofs, especially those based on Gauss's Lemma, [E.g. Kronecker's proof (Lemmermeyer, ex. p. 31, 1.34) is to use Gauss's lemma to establish that:and then switch "p" and "q".] explicitly calculate this formula.
The supplementary laws using Legendre symbols
Legendre's attempt to prove reciprocity is based on a theorem of his:
E.g., Théorème I is handled by letting "a" ≡ 1 and "b" ≡ 3 (mod 4) be primes and assuming that and, contrary the theorem, that Then has a solution, and taking congruences (mod 4) leads to a contradiction.
This technique doesn't work for Théorème VIII. Let "b" ≡ "B" ≡ 3 (mod 4), and assume Then if there is another prime "p" ≡ 1 (mod 4) such that the solvability of leads to a contradiction (mod 4). But Legendre was unable to prove there has to be such a prime p; he was later able to show that all that is required is "Legendre's lemma":
but he couldn't prove that either. Hilbert symbol (below) discusses how techniques based on the existence of solutions to can be made to work.
Gauss first proves [Gauss, DA, arts 108-116] the supplementary laws. He sets [Gauss, DA, arts 117-123] the basis for induction by proving the theorem for ±3 and ±5. Noting [Gauss, DA, arts 130] that it is easier to state for –3 and +5 than it is for +3 or –5, he states [Gauss, DA, Art 131] the general theorem in the form:
If "p" is a prime of the form 4"n"+1 then "p", but if "p" is of the form 4"n"+3 then –"p", is a quadratic residue (resp. nonresidue) of every prime, which, with a positive sign, is a residue (resp. nonresidue) of "p".
In the next sentence, he christens it the fundamental theorem (Gauss never used the word "reciprocity").
Introducing the notation "a" R "b" (resp. "a" N "b") to mean "a" is a quadratic residue (resp. nonresidue) (mod "b"), and letting "a", "a"′, etc represent positive primes ≡ 1 (mod 4) and "b", "b"′, etc positive primes ≡ 3 (mod 4), he breaks it out into the same 8 cases as Legendre:
In the next Article he generalizes this to what are basically the rules for the Jacobi symbol (below). Letting "A", "A"′, etc represent any (prime or composite) positive numbers ≡ 1 (mod 4) and "B", "B"′, etc. positive numbers ≡ 3 (mod 4):
All of these cases take the form "if a prime is a residue (mod a composite), then the composite is a residue or nonresidue, depending on the congruences (mod 4) (mod the prime)". He proves that these follow from cases 1) - 8).
Gauss needed, and was able to prove, [Gauss, DA, arts. 125-129] a lemma similar to the one Legendre needed:
The proof [Gauss, DA, arts 135-144] of quadratic reciprocity is by complete induction (i.e. assuming it is true for all numbers less than "n" allows the deduction it is true for "n") for each of the cases 1) to 8).
Gauss's version in Legendre symbols
These can be combined:
A number of proofs of the theorem, especially those based on
Gauss sums, [Because the basic Gauss sum equals ] or the splitting of primes in algebraic number fields, [Because the quadratic field is a subfield of the cyclotomic field ] derive this formula.
This form of quadratic reciprocity is derived from Euler's work: [Ireland & Rosen, p 60-61.]
Gauss's fourth proof [Gauss, "Summierung gewisser Reihen von besonderer Art", reprinted in "Untersuchumgen uber hohere Arithmetik", pp.463-495] consists of proving this theorem (by comparing two formulas for the value of Gauss sums) and then restricting it to two primes: Let "a", "b", "c", ... be unequal positive odd primes, whose product is "n", and let "m" be the number of them that are ≡ 3 (mod 4); check whether "n"/"a" is a residue of "a", whether "n"/"b" is a residue of "b", .... The number of nonresidues found will be even when "m" ≡ 0, 1 (mod 4), and it will be odd if "m" ≡ 2, 3 (mod 4).
He gives the example. Let "a" = 3, "b" = 5, "c" = 7, and "d" = 11. Three of these, 3, 7, and 11 ≡ 3 (mod 4), so "m" ≡ 3 (mod 4).
5×7×11 R 3; 3×7×11 R 5; 3×5×11 R 7; and 3×5×7 N 11, so there are an odd number of nonresidues.
Eisenstein [Lemmermeyer, Th. 2.28, pp 63-65] formulates this:
Mordell [Lemmermeyer, ex. 1.9, p. 28] proved that this is equivalent to quadratic reciprocity:
Jacobi symbolis a generalization of the Legendre symbol; the main difference is that the bottom number has to be positive and odd, but does not have to be prime. If it is prime, the two symbols agree. It obeys the same rules of manipulation as the Legendre symbol. In particular
and if both numbers are positive and odd (this is sometimes called "Jacobi's reciprocity law"):
However, if the Jacobi symbol is +1 and the bottom number is composite, it does not necessarily mean that the top number is a quadratic residue of the bottom one. Gauss's cases 9) - 14) above can be expressed in terms of Jacobi symbols:
and since "p" is prime the left hand side is a Legendre symbol, and we know whether "M" is a residue (mod "p") or not.
The formulas listed in the preceding section are true for Jacobi symbols as long as the symbols are defined. Euler's formula may be written
and 2 is a residue mod the primes 7, 23 and 31: 32 ≡ 2 (mod 7), 52 ≡ 2 (mod 23), and 82 ≡ 2 (mod 31), but 2 is not a quadratic residue (mod 5), so it can't be one (mod 15). This is related to the problem Legendre had: if we know that , we know that "a" is a nonresidue modulo every prime in the arithmetic series "m" + 4"a", "m" + 8"a", ..., if there "are" any primes in this series, but that wasn't proved until decades [By
Dirichletin 1837] after Legendre.
Eisenstein's formula requires relative primality conditions (which are true if the numbers are prime)
The quadratic reciprocity law can be formulated in terms of the
Hilbert symbolwhere "a" and "b" are any two nonzero rational numbers and "v" runs over all the non-trivial absolute values of the rationals (the archimedean one and the "p"-adic absolute values for primes "p"). The Hilbert symbol is 1 or −1. It is defined to be 1 if and only if the equation has a solution in the completionof the rationals at "v" other than . The Hilbert reciprocity law states that , for fixed "a" and "b" and varying "v", is 1 for all but finitely many "v" and the product of over all "v" is 1. (This formally resembles the residue theorem from complex analysis.)
The proof of Hilbert reciprocity reduces to checking a few special cases, and the non-trivial cases turn out to be equivalent to the main law and the two supplementary laws of quadratic reciprocity for the Legendre symbol. There is no kind of reciprocity in the Hilbert reciprocity law; its name simply indicates the historical source of the result in quadratic reciprocity. Unlike quadratic reciprocity, which requires sign conditions (namely positivity of the primes involved) and a special treatment of the prime 2, the Hilbert reciprocity law treats all absolute values of the rationals on an equal footing. Therefore it is a more natural way of expressing quadratic reciprocity with a view towards generalization: the Hilbert reciprocity law extends with very few changes to all
global fields and this extension can rightly be considered a generalization of quadratic reciprocity to all global fields.
The generalizations of quadratic reciprocity quickly take us from the realm of integer arithmetic into
algebraic number theory.
For example, Gauss investigated biquadratic (or quartic = fourth power) reciprocity. In his first [C. F. Gauss, Theorie der biquadratischen Reste, Comm. Soc. Reg. Sci. Gottingen (1828); reprinted in "Untersuchungen uber hohere Arithmetik", pp. 511-533] paper he proves a number of theorems, the most important being that if "p" ≡ 1 (mod 4) then "x"4 ≡ 2 (mod "p") has a solution if and only if "p" = "a"2 + 64"b"2 where "a" and "b" are integers.
If "p" ≡ 3 (mod 4) then every quadratic residue (mod "p") is also a biquadratic residue. If "r" ≡ "x"2 (mod "p") and "x" is a quadratic residue itself, then "r" will be a fourth power; and if "x" is a nonresidue, –x is a residue, since –1 is a nonresidue (mod "p").This is done within ordinary integer arithmetic.
The second paper [C. F. Gauss, Theoria residuorum biquadraticorum. Commentatio secunda., Comm. Soc. Reg. Sci. Gottingen 7 (1832) 1-34; reprinted in Werke, Georg Olms Verlag, Hildesheim, 1973, pp. 93-148, and in "Untersuchungen uber hohere Arithmetik", pp. 534-589] is famous for his introduction of the
Gaussian integers, (complex numbers with integer real and imaginary parts). He shows that primes ≡ 1 (mod 4) split into products of two primes there (eg., 13 = (3 + 2"i")(3 – 2"i")), proves the unique factorization theorem, and introduces terms that are fundamental in algebraic number theory, such as norm, associate, and unit. The statement of the quartic reciprocity law is simple in this domain, [He doesn't prove it in this paper, and never published the third installment; it was first proven by Eisenstein.] and he notes that cubic reciprocityis simplest in the domain of Eisenstein integers. Part of the reason for this is that there are four fourth roots of 1 (usually called "roots of unity") in the Gaussian integers (±1, ±"i"), and the Eisenstein integers have three cubic roots of unity. The analogues of the Legendre symbol in these domains have values that are roots of unity, just as the quadratic version takes on the values ±1, the square roots of 1. Extending this to higher powers led to many advances in algebra and number theory.
The other extension is the law of quadratic reciprocity itself in these domains. Again, Gauss led the way, stating quadratic reciprocity in the Gaussian integers. [In the first paper on biquadratic resiprocity; Lemmermeyer, p.154, gives Dirichlet's short proof, which uses quadratic reciprocity; Ireland & Rosen, p. 64, ex. 26]
Lemmermeyer's "Reciprocity Laws" (in the references), covers all of this and much more.
Gauss's lemma (number theory)
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.
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. An exercise [Ireland & Rosen, Ch. 13 exercise 26 (p 202)] says it all:
Count the number of proofs to the law of quadratic reciprocity given thus far in this book and devise another one.
last1 = Gauss | first1 = Carl Friedrich
last2 = Clarke | first2 = Arthur A. (translator into English)
title = Disquisitiones Arithemeticae (Second, corrected edition)
location = New York
date = 1986
isbn = 0387962549
last1 = Gauss | first1 = Carl Friedrich
last2 = Maser | first2 = H. (translator into German)
title = Untersuchungen uber hohere Arithmetik (Disquisitiones Arithemeticae & other papers on number theory) (Second edition)
publisher = Chelsea
location = New York
date = 1965
isbn = 0-8284-0191-8
last1 = Lemmermeyer | first1 = Franz
title = Reciprocity Laws: from Euler to Eisenstein
location = Berlin
date = 2000
isbn = 3-540-66967-4
last1 = Ireland | first1 = Kenneth
last2 = Rosen | first2 = Michael
title = A Classical Introduction to Modern Number Theory (second edition)
location = New York
date = 1990
isbn = 0-387-97329-X
* [http://mathworld.wolfram.com/QuadraticReciprocityTheorem.html Quadratic Reciprocity Theorem] from
* [http://www.math.nmsu.edu/~history/schauspiel/schauspiel.html A "play" comparing two proofs of the quadratic reciprocity law]
* [http://planetmath.org/encyclopedia/ProofOfQuadraticReciprocityRule.html A proof of this theorem] at PlanetMath
* [http://www.mathpages.com/home/kmath075.htm A different proof] at MathPages
* [http://www.rzuser.uni-heidelberg.de/~hb3/fchrono.html F. Lemmermeyer's chronology and bibliography of proofs of the Quadratic Reciprocity Law] (224 proofs!)
Wikimedia Foundation. 2010.
Look at other dictionaries:
quadratic reciprocity — noun Mathematical theorem relating the Jacobi symbol to the inverted , essentially relating the question of whether a is a square modulo b to the opposite question of whether b is a square modulo a (or modulo the prime factors) … Wiktionary
Proofs of quadratic reciprocity — In the mathematical field of number theory, the law of quadratic reciprocity, like the Pythagorean theorem, has lent itself to an unusual number of proofs. Several hundred proofs of the law of quadratic reciprocity have been found.Proofs that are … Wikipedia
Reciprocity — may refer to: Reciprocity (Canadian politics) Reciprocity (photography), the relationship between the intensity of the light and duration of the exposure that result in identical exposure Traffic violations reciprocity where non resident drivers… … Wikipedia
Reciprocity law — may refer to:* Reciprocity law (mathematics), (typefied by the law of quadratic reciprocity) * Reciprocity (photography) … Wikipedia
Quadratic residue — In number theory, an integer q is called a quadratic residue modulo n if it is congruent to a perfect square modulo n; i.e., if there exists an integer x such that: Otherwise, q is called a quadratic nonresidue modulo n. Originally an abstract… … Wikipedia
Quadratic — In mathematics, the term quadratic describes something that pertains to squares, to the operation of squaring, to terms of the second degree, or equations or formulas that involve such terms. Quadratus is Latin for square . Mathematics Algebra… … Wikipedia
Quadratic field — In algebraic number theory, a quadratic field is an algebraic number field K of degree two over Q. It is easy to show that the map d ↦ Q(√d) is a bijection from the set of all square free integers d ≠ 0, 1 to the set of… … Wikipedia
Reciprocity (mathematics) — In mathematics, reciprocity may mean:* Quadratic reciprocity, a fundamental result in number theory. Generalisations include: **cubic reciprocity **biquadratic reciprocity **higher reciprocity laws **Artin reciprocity **Weil reciprocity for… … Wikipedia
quadratic — 1. adjective a) square shaped b) of a polynomial, involving the second power (square) of a variable but no higher powers, as . 2. noun A quadratic polynomial, function or equation. See Also: quadrate, quadratic equation, quadratic fo … Wiktionary
Quadratic Gauss sum — For the general type of Gauss sums see Gaussian period, Gauss sumIn mathematics, quadratic Gauss sums are certain sums over exponential functions with quadratic argument. They are named after Carl Friedrich Gauss, who studied them… … Wikipedia