From Wikipedia, the free encyclopedia

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.

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.

Contents 1 An elementary statement of the theorem 1.1 Case I: If p = 1 mod 4 or q = 1 mod 4 (or both) 1.2 Case II: If p = 3 mod 4 AND q = 3 mod 4 1.3 The supplementary theorems 1.4 Table illustrating quadratic reciprocity 2 Statement in terms of the Legendre symbol 3 Statement in terms of the Hilbert symbol 4 Generalizations 5 See also 6 External links

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).

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.

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 an odd prime. 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 green 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

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 q is of the form 4k + 1

if q is of the form 4k + 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 4k + 1

if both p and q are of the form 4k + 3

Since (p − 1)(q − 1)/4 is odd if and only if both primes are of the form 4k + 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 (a,b)_v 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 (a,b)_v is 1 or −1. The Hilbert reciprocity law states that (a,b)_v, for fixed a and b and varying v, is 1 for all but finitely many v and the product of (a,b)_v 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
• Quadratic Reciprocity - The Jewel of Arithmetic at MathPages