العربية
中国
Français
Deutsch
Ελληνική
हिन्दी
Italiano
日本語
Português
Русский
EspañolQUADRATIC RECIPROCITY
The 'law of quadratic reciprocity' is a theorem from number theory which considers two distinct odd prime numbers, ''p'' and ''q'', and the statements
: A: ''p'' is a square mod ''q'', and
: B: ''q'' is a square mod ''p''.
It asserts that
★ If 'both' ''p'' and ''q'' are congruent to 3 (mod 4), then exactly 'one' of (A) and (B) is true
★ Otherwise, either 'both' (A) and (B) are true, or 'neither' of them is true.
Thus it
connects the solvability of two related quadratic equations in modular arithmetic. As a consequence, it allows us to determine the ''solvability'' of any quadratic equation in modular arithmetic, even though it does not provide an efficient method for actually ''finding'' solutions.
The theorem was conjectured by Euler and Legendre and first satisfactorily proven by Gauss. Gauss called it the 'golden theorem' and was so fond of it that he went on to provide eight separate proofs over his lifetime. Recently a new proof has been discovered by manipulating Combinatorial Nullstellensatz.
Franz Lemmermeyer's book ''Reciprocity Laws: From Euler to Eisenstein'', published in 2000, collects literature citations for 196 different published proofs for the quadratic reciprocity law.
Suppose that ''p'' and ''q'' are two distinct odd prime numbers. The theorem relates the solvability of the equation
:
to the solvability of the equation
:
(''see modular arithmetic'').
i.e. (A) states that ''p'' is a square modulo ''q'', while (B) states that ''q'' is a square modulo ''p''. There are two cases, either 'both' ''p'' and ''q'' are congruent to 3 (mod 4) (Case II), or they are not (Case I).
=== Case I: If ''p'' = 1 mod 4 or ''q'' = 1 mod 4 (or both)===
In this case, the theorem says that (A) has a solution ''if and only if'' (B) has a solution. That is, either they both have solutions, or they both do not.
For example, if ''p'' = 13 and ''q'' = 17 (both of which are congruent to 1 mod 4), then (A) has the solution
:
and (B) has a solution
:
On the other hand, if ''p'' = 5 and ''q'' = 13, then neither (A) nor (B) has a solution (this can be checked by simply listing all of the squares modulo 5 and modulo 13).
The theorem says nothing about the actual solutions themselves, only about whether they exist.
=== Case II: If ''p'' = 3 mod 4 'AND' ''q'' = 3 mod 4===
In this case, the theorem says that (A) has a solution if and only if (B) does ''not'' have a solution.
For example, if ''p'' = 7 and ''q'' = 19, then (A) has the solution
:
but (B) does not have a solution.
There are two extra statements which round out the above laws. Suppose again that ''p'' is a prime, not equal to 2. The first says that the equation
:
has a solution if ''p'' is congruent to 1 mod 4, but does not have a solution if it is congruent to 3 mod 4. For example, if ''p'' = 29, there is a solution
:
but for ''p'' = 7 there is no solution.
The second says that the equation
:
has a solution if and only if ''p'' is congruent to 1 or 7 modulo 8, but not if it is congruent to 3 or 5 modulo 8.
The following table illustrates the law of quadratic reciprocity for primes up to 50. In each cell, the first symbol (checkmark or cross) indicates whether ''p'' is a square modulo ''q''; the second symbol indicates whether ''q'' is a square modulo ''p''. The ''blue'' cells are those where either ''p'' or ''q'' is congruent to 1 modulo 4; the ''red'' cells are those where both ''p'' and ''q'' are congruent to 3 modulo 4. The law of quadratic reciprocity is interpreted as follows: every blue cell contains two ''identical'' symbols, and every red cell contains two ''opposite'' symbols.
The theorem can be stated more compactly using the Legendre symbol:
:
The theorem states that if ''p'' and '' q'' are two different odd primes, then, using Gauss's original formulation:
: if ''p'' is of the form 4''k'' + 1
: if ''p'' is of the form 4''k'' + 3
Which is also equivalent to the very similar form, commonly used today:
: if one or both of ''p'' and ''q'' are of the form 4''k'' + 1
: if both ''p'' and ''q'' are of the form 4''k'' + 3
Since (''p'' − 1)(''q'' − 1)/4 is odd if and only if both primes are of the form 4''k'' + 3, we have another commonly-used form:
:
This is called the main law of quadratic reciprocity, in comparison to the following two
supplementary laws (really, theorems): for any odd prime ''p'',
:
and
:
The main law of quadratic reciprocity extends to the Jacobi symbol: for positive odd integers ''m'' and ''n'' which are relatively prime,
:.
Notationally, this looks identical to the main law except the parameters are not necessarily prime anymore.
The supplementary laws for the Legendre symbol also remain true for the Jacobi symbol, with the odd prime ''p'' replaced by
an odd positive integer ''m''.
The quadratic reciprocity law can be formulated in terms of the Hilbert symbol where ''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. 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 extensions can
rightly be considered a generalization of quadratic reciprocity to all global fields.
There is a law of cubic reciprocity as well quartic (biquadratic) reciprocity and other higher reciprocity laws; but since two of the cube roots of 1 (root of unity) are not real, cubic reciprocity is outside the arithmetic of the rational numbers (and the same applies to higher laws).
★ Gauss's lemma (number theory)
★ Jacobi symbol
★ Artin reciprocity
★ Quadratic Reciprocity Theorem from MathWorld
★ A ''play'' comparing two proofs of the quadratic reciprocity law
★ A proof of this theorem, at PlanetMath
: A: ''p'' is a square mod ''q'', and
: B: ''q'' is a square mod ''p''.
It asserts that
★ If 'both' ''p'' and ''q'' are congruent to 3 (mod 4), then exactly 'one' of (A) and (B) is true
★ Otherwise, either 'both' (A) and (B) are true, or 'neither' of them is true.
Thus it
connects the solvability of two related quadratic equations in modular arithmetic. As a consequence, it allows us to determine the ''solvability'' of any quadratic equation in modular arithmetic, even though it does not provide an efficient method for actually ''finding'' solutions.
The theorem was conjectured by Euler and Legendre and first satisfactorily proven by Gauss. Gauss called it the 'golden theorem' and was so fond of it that he went on to provide eight separate proofs over his lifetime. Recently a new proof has been discovered by manipulating Combinatorial Nullstellensatz.
Franz Lemmermeyer's book ''Reciprocity Laws: From Euler to Eisenstein'', published in 2000, collects literature citations for 196 different published proofs for the quadratic reciprocity law.
An elementary statement of the theorem
Suppose that ''p'' and ''q'' are two distinct odd prime numbers. The theorem relates the solvability of the equation
:
to the solvability of the equation
:
(''see modular arithmetic'').
i.e. (A) states that ''p'' is a square modulo ''q'', while (B) states that ''q'' is a square modulo ''p''. There are two cases, either 'both' ''p'' and ''q'' are congruent to 3 (mod 4) (Case II), or they are not (Case I).
=== Case I: If ''p'' = 1 mod 4 or ''q'' = 1 mod 4 (or both)===
In this case, the theorem says that (A) has a solution ''if and only if'' (B) has a solution. That is, either they both have solutions, or they both do not.
For example, if ''p'' = 13 and ''q'' = 17 (both of which are congruent to 1 mod 4), then (A) has the solution
:
and (B) has a solution
:
On the other hand, if ''p'' = 5 and ''q'' = 13, then neither (A) nor (B) has a solution (this can be checked by simply listing all of the squares modulo 5 and modulo 13).
The theorem says nothing about the actual solutions themselves, only about whether they exist.
=== Case II: If ''p'' = 3 mod 4 'AND' ''q'' = 3 mod 4===
In this case, the theorem says that (A) has a solution if and only if (B) does ''not'' have a solution.
For example, if ''p'' = 7 and ''q'' = 19, then (A) has the solution
:
but (B) does not have a solution.
The supplementary theorems
There are two extra statements which round out the above laws. Suppose again that ''p'' is a prime, not equal to 2. The first says that the equation
:
has a solution if ''p'' is congruent to 1 mod 4, but does not have a solution if it is congruent to 3 mod 4. For example, if ''p'' = 29, there is a solution
:
but for ''p'' = 7 there is no solution.
The second says that the equation
:
has a solution if and only if ''p'' is congruent to 1 or 7 modulo 8, but not if it is congruent to 3 or 5 modulo 8.
Table illustrating quadratic reciprocity
The following table illustrates the law of quadratic reciprocity for primes up to 50. In each cell, the first symbol (checkmark or cross) indicates whether ''p'' is a square modulo ''q''; the second symbol indicates whether ''q'' is a square modulo ''p''. The ''blue'' cells are those where either ''p'' or ''q'' is congruent to 1 modulo 4; the ''red'' cells are those where both ''p'' and ''q'' are congruent to 3 modulo 4. The law of quadratic reciprocity is interpreted as follows: every blue cell contains two ''identical'' symbols, and every red cell contains two ''opposite'' symbols.
| ''p'' | |||||||||||||||
| ''q'' | '3' | '5' | '7' | '11' | '13' | '17' | '19' | '23' | '29' | '31' | '37' | '41' | '43' | '47' | |
| ' 3 ' | ✗ ✗ | ✓ ✗ | ✗ ✓ | ✓ ✓ | ✗ ✗ | ✓ ✗ | ✗ ✓ | ✗ ✗ | ✓ ✗ | ✓ ✓ | ✗ ✗ | ✓ ✗ | ✗ ✓ | ||
| ' 5 ' | ✗ ✗ | ✗ ✗ | ✓ ✓ | ✗ ✗ | ✗ ✗ | ✓ ✓ | ✗ ✗ | ✓ ✓ | ✓ ✓ | ✗ ✗ | ✓ ✓ | ✗ ✗ | ✗ ✗ | ||
| ' 7 ' | ✗ ✓ | ✗ ✗ | ✓ ✗ | ✗ ✗ | ✗ ✗ | ✗ ✓ | ✓ ✗ | ✓ ✓ | ✗ ✓ | ✓ ✓ | ✗ ✗ | ✓ ✗ | ✗ ✓ | ||
| ' 11 ' | ✓ ✗ | ✓ ✓ | ✗ ✓ | ✗ ✗ | ✗ ✗ | ✗ ✓ | ✓ ✗ | ✗ ✗ | ✓ ✗ | ✓ ✓ | ✗ ✗ | ✗ ✓ | ✓ ✗ | ||
| ' 13 ' | ✓ ✓ | ✗ ✗ | ✗ ✗ | ✗ ✗ | ✓ ✓ | ✗ ✗ | ✓ ✓ | ✓ ✓ | ✗ ✗ | ✗ ✗ | ✗ ✗ | ✓ ✓ | ✗ ✗ | ||
| ' 17 ' | ✗ ✗ | ✗ ✗ | ✗ ✗ | ✗ ✗ | ✓ ✓ | ✓ ✓ | ✗ ✗ | ✗ ✗ | ✗ ✗ | ✗ ✗ | ✗ ✗ | ✓ ✓ | ✓ ✓ | ||
| ' 19 ' | ✗ ✓ | ✓ ✓ | ✓ ✗ | ✓ ✗ | ✗ ✗ | ✓ ✓ | ✓ ✗ | ✗ ✗ | ✗ ✓ | ✗ ✗ | ✗ ✗ | ✓ ✗ | ✓ ✗ | ||
| ' 23 ' | ✓ ✗ | ✗ ✗ | ✗ ✓ | ✗ ✓ | ✓ ✓ | ✗ ✗ | ✗ ✓ | ✓ ✓ | ✓ ✗ | ✗ ✗ | ✓ ✓ | ✗ ✓ | ✓ ✗ | ||
| ' 29 ' | ✗ ✗ | ✓ ✓ | ✓ ✓ | ✗ ✗ | ✓ ✓ | ✗ ✗ | ✗ ✗ | ✓ ✓ | ✗ ✗ | ✗ ✗ | ✗ ✗ | ✗ ✗ | ✗ ✗ | ||
| ' 31 ' | ✗ ✓ | ✓ ✓ | ✓ ✗ | ✗ ✓ | ✗ ✗ | ✗ ✗ | ✓ ✗ | ✗ ✓ | ✗ ✗ | ✗ ✗ | ✓ ✓ | ✗ ✓ | ✓ ✗ | ||
| ' 37 ' | ✓ ✓ | ✗ ✗ | ✓ ✓ | ✓ ✓ | ✗ ✗ | ✗ ✗ | ✗ ✗ | ✗ ✗ | ✗ ✗ | ✗ ✗ | ✓ ✓ | ✗ ✗ | ✓ ✓ | ||
| ' 41 ' | ✗ ✗ | ✓ ✓ | ✗ ✗ | ✗ ✗ | ✗ ✗ | ✗ ✗ | ✗ ✗ | ✓ ✓ | ✗ ✗ | ✓ ✓ | ✓ ✓ | ✓ ✓ | ✗ ✗ | ||
| ' 43 ' | ✗ ✓ | ✗ ✗ | ✗ ✓ | ✓ ✗ | ✓ ✓ | ✓ ✓ | ✗ ✓ | ✓ ✗ | ✗ ✗ | ✓ ✗ | ✗ ✗ | ✓ ✓ | ✓ ✗ | ||
| ' 47 ' | ✓ ✗ | ✗ ✗ | ✓ ✗ | ✗ ✓ | ✗ ✗ | ✓ ✓ | ✗ ✓ | ✗ ✓ | ✗ ✗ | ✗ ✓ | ✓ ✓ | ✗ ✗ | ✗ ✓ | ||
Statement in terms of the Legendre symbol
Gauss' formulation in the ''Disquisitiones Arithmeticae''
The theorem can be stated more compactly using the Legendre symbol:
:
The theorem states that if ''p'' and '' q'' are two different odd primes, then, using Gauss's original formulation:
: if ''p'' is of the form 4''k'' + 1
: if ''p'' is of the form 4''k'' + 3
Which is also equivalent to the very similar form, commonly used today:
: if one or both of ''p'' and ''q'' are of the form 4''k'' + 1
: if both ''p'' and ''q'' are of the form 4''k'' + 3
Since (''p'' − 1)(''q'' − 1)/4 is odd if and only if both primes are of the form 4''k'' + 3, we have another commonly-used form:
:
This is called the main law of quadratic reciprocity, in comparison to the following two
supplementary laws (really, theorems): for any odd prime ''p'',
:
and
:
The main law of quadratic reciprocity extends to the Jacobi symbol: for positive odd integers ''m'' and ''n'' which are relatively prime,
:.
Notationally, this looks identical to the main law except the parameters are not necessarily prime anymore.
The supplementary laws for the Legendre symbol also remain true for the Jacobi symbol, with the odd prime ''p'' replaced by
an odd positive integer ''m''.
Statement in terms of the Hilbert symbol
The quadratic reciprocity law can be formulated in terms of the Hilbert symbol where ''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. 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 extensions can
rightly be considered a generalization of quadratic reciprocity to all global fields.
Generalizations
There is a law of cubic reciprocity as well quartic (biquadratic) reciprocity and other higher reciprocity laws; but since two of the cube roots of 1 (root of unity) are not real, cubic reciprocity is outside the arithmetic of the rational numbers (and the same applies to higher laws).
See also
★ Gauss's lemma (number theory)
★ Jacobi symbol
★ Artin reciprocity
External links
★ Quadratic Reciprocity Theorem from MathWorld
★ A ''play'' comparing two proofs of the quadratic reciprocity law
★ A proof of this theorem, at PlanetMath
This article provided by Wikipedia. To edit the contents of this article, click here for original source.
psst.. try this: add to faves
