Quadratic reciprocity

From Free net encyclopedia

In mathematics, in number theory, the law of quadratic reciprocity 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.

It 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

[edit]

An elementary statement of the theorem

Suppose that p and q are two different prime numbers, neither of which is 2. The theorem relates the solvability of the equation

<math>x^2\equiv p\ ({\rm mod}\ q) \qquad (A)</math>

to the solvability of the equation

<math>x^2\equiv q\ ({\rm mod}\ p) \qquad (B)</math>

(see modular arithmetic). There are two cases, depending on whether p and q are congruent to 1 or to 3 (mod 4).

[edit]

If at least one of p or q is congruent to 1 mod 4

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

<math>8^2 \equiv 13 \pmod{17}, \,</math>

and (B) has a solution

<math>2^2 \equiv 17 \pmod{13} \,.</math>

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.

[edit]

If both p and q are congruent to 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

<math>8^2 \equiv 7 \pmod{19}, \,</math>

but (B) does not have a solution.

[edit]

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

<math>x^2 \equiv -1 \pmod p\,</math>

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

<math>{12}^2 \equiv -1 \pmod{29}, \,</math>

but for p = 7 there is no solution.

The second says that the equation

<math>x^2 \equiv 2 \pmod p\,</math>

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.

[edit]

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  ✓ ✗ ✗ ✗ ✓ ✗ ✗ ✓ ✗ ✗ ✓ ✓ ✗ ✓ ✗ ✓ ✗ ✗ ✗ ✓ ✓ ✓ ✗ ✗ ✗ ✓
[edit]

Statement in terms of the Legendre symbol

Image:Disquisitiones-Arithmeticae-p133.jpg The theorem can be stated more compactly using the Legendre symbol:

<math>\left(\frac{a}{p}\right)=\left\{\begin{matrix}1 & \mathrm{if}\ a\ \mathrm{is\ a\ square\ modulo\ }p, \\

0 & \mathrm{if\ } p\ \mathrm{divides\ }a, \\ -1 & \mathrm{otherwise,}\end{matrix}\right.</math>

The theorem states that if p and q are two different odd primes, then, using Gauss's original formulation:

<math> \left(\frac{p}{q}\right) = \left(\frac{q}{p}\right)</math> if p is of the form 4k + 1
<math> \left(\frac{p}{q}\right) = \left(\frac{-q}{p}\right)</math> if p is of the form 4k + 3

Which is also equivalent to the very similar form, commonly used today:

<math> \left(\frac{p}{q}\right) = \left(\frac{q}{p}\right)</math> if one or both of p and q are of the form 4k + 1
<math> \left(\frac{p}{q}\right) = -\left(\frac{q}{p}\right)</math> if both p and q are of the form 4k + 3

Since <math>(p-1)(q-1)/4</math> is odd if and only if both primes are of the form 4k + 3, we have another commonly-used form:

<math> \left(\frac{p}{q}\right) \left(\frac{q}{p}\right) = (-1)^{(p-1)(q-1)/4}</math>

This is called the main law of quadratic reciprocity, in comparison to the following two supplementary laws (really, theorems): for any odd prime p,

<math>\left(\frac{-1}{p}\right) = (-1)^{(p-1)/2},</math>

and

<math>\left(\frac{2}{p}\right) = (-1)^{(p^2-1)/8}.</math>

The main law of quadratic reciprocity extends to the Jacobi symbol: for positive odd integers m and n which are relatively prime,

<math> \left(\frac{m}{n}\right) \left(\frac{n}{m}\right) = (-1)^{(m-1)(n-1)/4}</math>.

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.

[edit]

Statement in terms of the Hilbert symbol

The quadratic reciprocity law can be formulated in terms of the Hilbert symbol <math>(a,b)_v</math> 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 <math>(a,b)_v</math> is 1 or -1. The Hilbert reciprocity law states that <math>(a,b)_v</math>, for fixed a and b and varying v, is 1 for all but finitely many v and the product of <math>(a,b)_v</math> 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 qudratic 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.

[edit]

Generalizations

There are cubic, quartic (biquadratic) 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).

[edit]

See also

[edit]

External links

es:Ley de reciprocidad cuadrática fr:Loi de réciprocité quadratique he:משפט ההדדיות הריבועית it:Reciprocità quadratica hu:Kvadratikus reciprocitás tétele ja:平方剰余の相互法則 pl:Prawo wzajemności reszt kwadratowych ru:Квадратичный закон взаимности fi:Neliönjäännöslause sv:Kvadratiska reciprocitetssatsen zh:二次互反律

Retrieved from "http://www.netipedia.com/index.php/Quadratic_reciprocity"