Quadratic reciprocity

From Wikipedia, the free encyclopedia

Law of Reciprocity redirects here. For the philosophical concept also known as the Golden Rule, see Ethic of 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 residue discusses algorithms for this.)

The theorem was conjectured by Euler and Legendre and first proven by Gauss.[1] He refers to it as the 'fundamental theorem' in the Disquisitiones Arithmeticae and his papers; privately he referred to it as the 'golden theorem'.[2] He was so fond of it that he provided eight separate proofs over his lifetime. There are over 200[3] 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.

Contents

[edit] 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.

[edit] Table of quadratic residues

Squares mod primes
n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
n2 1 4 9 16 25 36 49 64 81 100 121 144 169 196 225 256 289 324 361 400 441 484 529 576 625
mod 3 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1
mod 5 1 4 4 1 0 1 4 4 1 0 1 4 4 1 0 1 4 4 1 0 1 4 4 1 0
mod 7 1 4 2 2 4 1 0 1 4 2 2 4 1 0 1 4 2 2 4 1 0 1 4 2 2
mod 11 1 4 9 5 3 3 5 9 4 1 0 1 4 9 5 3 3 5 9 4 1 0 1 4 9
mod 13 1 4 9 3 12 10 10 12 3 9 4 1 0 1 4 9 3 12 10 10 12 3 9 4 1
mod 17 1 4 9 16 8 2 15 13 13 15 2 8 16 9 4 1 0 1 4 9 16 8 2 15 13
mod 19 1 4 9 16 6 17 11 7 5 5 7 11 17 6 16 9 4 1 0 1 4 9 16 6 17
mod 23 1 4 9 16 2 13 3 18 12 8 6 6 8 12 18 3 13 2 16 9 4 1 0 1 4
mod 29 1 4 9 16 25 7 20 6 23 13 5 28 24 22 22 24 28 5 13 23 6 20 7 25 16
mod 31 1 4 9 16 25 5 18 2 19 7 28 20 14 10 8 8 10 14 20 28 7 19 2 18 5
mod 37 1 4 9 16 25 36 12 27 7 26 20 33 21 11 3 34 30 28 28 30 34 3 11 21 33
mod 41 1 4 9 16 25 36 8 23 40 18 39 21 5 32 20 10 2 37 33 31 31 33 37 2 10
mod 43 1 4 9 16 25 36 6 21 38 14 35 15 40 24 10 41 31 23 17 13 11 11 13 17 23
mod 47 1 4 9 16 25 36 2 17 34 6 27 3 28 8 37 21 7 42 32 24 18 14 12 12 14

This table is complete for primes less than 50. To check whether a number n is a quadratic residue mod one of these primes p, find a ≡ n (mod p) and 0 ≤ a < p. If a is in row p it is a residue (mod p); if it is not in row p of the table, it is a nonresidue (mod p).

The quadratic reciprocity law is the statement that certain patterns found in the table are true in general.

[edit] –1 and the first supplement

First of all, for which prime numbers is –1 a quadratic residue? Examining the table, we find –1 in rows 5, 13, 17, 29, 37, and 41 but not in rows 3, 7, 11, 19, 23, 31, 43 or 47.

(–1 ≡ 2 (mod 3), –1 ≡ 4 (mod 5), –1 ≡ 10 (mod 11), etc.)

The former primes are all ≡ 1 (mod 4), and the latter are all ≡ 3 (mod 4). This leads to

The first supplement to quadratic reciprocity:

\mbox{The congruence }x^2 \equiv -1 \pmod p \mbox{ is solvable if and only if }p\equiv 1 \pmod 4.

[edit] ±2 and the second supplement

For which prime numbers is 2 a quadratic residue? Examining the table, we find 2 in rows 7, 17, 23, 31, 41, and 47, but not in rows 3, 5, 11, 13, 19, 29, 37, or 43.

The former primes are all ≡ ±1 (mod 8), and the latter are all ≡ ±3 (mod 8). This leads to

The second supplement to quadratic reciprocity:

\mbox{The congruence }x^2 \equiv 2 \pmod p \mbox{ is solvable if and only if }p\equiv \pm 1 \pmod 8.

–2 is in rows 3, 11, 17, 19, 41, 43, but not in rows 5, 7, 13, 23, 29, 31, 37, or 47. The former are ≡ 1 or ≡ 3 (mod 8), and the latter are ≡ 5 or ≡ 7 (mod 8).

[edit] ±3

3 is in rows 11, 13, 23, 37, and 47, but not in rows 5, 7, 17, 19, 29, 31, 41, or 43.

The former are ≡ ±1 (mod 12) and the latter are all ≡ ±5 (mod 12).

–3 is in rows 7, 13, 19, 31, 37, and 43 but not in rows 5, 11, 17, 23, 29, 41, or 47. The former are ≡ 1 (mod 3) and the latter ≡ 2 (mod 3).

Since the only residue (mod 3) is 1, we see that –3 is a quadratic residue modulo every prime which is a residue (mod 3).

[edit] ±5

5 is in rows 11, 19, 29, 31, and 41 but not in rows 3, 7, 13, 17, 23, 37, 43, or 47.

The former are ≡ ±1 (mod 5) and the latter are ≡ ±2 (mod 5).

Since the only residues (mod 5) are ±1, we see that 5 is a quadratic residue modulo every prime which is a residue (mod 5).

–5 is in rows 3, 7, 23, 29, 41, 43, and 47 but not in rows 11, 13, 17, 19, 31, or 37. The former are ≡ 1, 3, 7, 9 (mod 20) and the latter are ≡ 11, 13, 17, 19 (mod 20).

[edit] Gauss's version

The observations about –3 and +5 continue to hold: –7 is a residue (mod p) if and only if p is a residue (mod 7), –11 is a residue (mod p) if and only if p is a residue (mod 11), +13 is a residule (mod p) if and only if p is a residue (mod 13), ...

The more complicated-looking rules for the quadratic characters of +3 and –5, which depend upon congruences (mod 12) and (mod 20) respectively, are simply the ones for –3 and +5 working with the first supplement.

For example, for –5 to be a residue (mod p), either both 5 and –1 have to be residues (mod p) or they both have to be nonresidues: i.e., p has to be ≡ ±1 (mod 5) and ≡ 1 (mod 4), which is the same thing as p ≡ 1 or 9 (mod 20), or p has to be ≡ ±2 mod 5 and ≡ 3 mod 4, which is the same as p ≡ 3 or 7 (mod 20). See Chinese remainder theorem.

The generalization of the rules for –3 and +5 are Gauss's statement of quadratic reciprocity:

\mbox{If }q \equiv 1 \pmod 4 \mbox{ then}

\mbox{the congruence }x^2 \equiv p \pmod q \mbox{ is solvable if and only if }x^2 \equiv q \pmod p \mbox{ is, but}

\mbox{If }q \equiv 3 \pmod 4 \mbox{ then}

\mbox{the congruence }x^2 \equiv p \pmod q \mbox{ is solvable if and only if }x^2 \equiv -q \pmod p \mbox{ is.}

These statements may be combined:

\mbox{Let }q^* = (-1)^\frac{q-1}{2}q. \mbox{ Then }

\mbox{the congruence }x^2 \equiv p \pmod q \mbox{ is solvable if and only if }x^2 \equiv q^* \pmod p \mbox{ is.}

[edit] Table showing quadratic characters of primes

"R"    q is a quadratic residue (mod p)      
"N"    q is a quadratic nonresidue (mod p)
q
3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
p 3   N R N R N R N N R R N R N N N R R N R R N N R
5 N   N R N N R N R R N R N N N R R N R N R N R N
7 N N   R N N N R R N R N R N R N N R R N R N N N
11 R R N   N N N R N R R N N R R R N R R N N N R R
13 R N N N   R N R R N N N R N R N R N N N R N N N
17 N N N N R   R N N N N N R R R R N R N N N R R N
19 N R R R N R   R N N N N R R N N R N N R N R N N
23 R N N N R N N   R R N R N R N R N N R R N N N N
29 N R R N R N N R   N N N N N R R N R R N N R N N
31 N R R N N N R N N   N R N R N R N R R N N N N R
37 R N R R N N N N N N   R N R R N N R R R N R N N
41 N R N N N N N R N R R   R N N R R N N R N R N N
43 N N N R R R N R N R N R   R R R N R N N R R N R
47 R N R N N R N N N N R N N   R R R N R N R R R R
53 N N R R R R N N R N R N R R   R N N N N N N R R
59 R R R N N R R N R N N R N N R   N N R N R N N N
61 R R N N R N R N N N N R N R N N   N N R N R N R
67 N N N N N R R R R N R N N R N R N   R R N R R N
71 R R N N N N R N R N R N R N N N N N   R R R R N
73 R N N N N N R R N N R R N N N N R R R   R N R R
79 N R N R R N R R N R N N N N N N N R N R   R R R
83 R N R R N R N R R R R R N N N R R N N N N   N N
89 N R N R N R N N N N N N N R R N N R R R R N   R
97 R N N R N N N N N R N N R R R N R N N R R N R  

[edit] Legendre's version

Another way to organize the data is to see which primes are residues mod which other primes, as illustrated in the above table. The entry in row p column q is R if q is a quadratic residue (mod p); if it is a nonresidue the entry is N.

If the row, or the column, or both, are ≡ 1 (mod 4) the entry is white; if both row and column are ≡ 3 (mod 4), it is beige.

The white entries are symmetric around the diagonal: The entry for row p, column q is R (resp N) if and only if the entry at row q, column p, is R (resp N).

The beige ones, on the other hand, are antisymmetric: The entry for row p, column q is R (resp N) if and only if the entry at row q, column p, is N (resp R).

This observation is Legendre's statement of quadratic reciprocity:

\mbox{If }p\equiv1\pmod4 \mbox{ or }q\equiv1\pmod4 \mbox{ (or both), then}
x^2 \equiv q \pmod p \mbox{ is solvable if and only if }x^2 \equiv p \pmod q\mbox{ is solvable.}
\mbox{If }p\equiv q \equiv 3 \pmod4, \mbox{ then}
x^2 \equiv q \pmod p \mbox{ is solvable if and only if }x^2 \equiv p \pmod q\mbox{ is not solvable.}

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.

[edit] Examples

Making up and checking examples to verify the many cases involved is easy using the tables. Say you want an example where p ≡ 1 (mod 4) and q ≡ 3 (mod 4), and they are both nonresidues of each other. Just find an entry in the second table like that, say 3 and 5. Then check the first table to see that neither number (or any number congruent to it) is in the relevant row.

The first table is complete for all primes less than 50, so if a number is not congruent to any number in row p, it is not a residue (mod p)

The discussion in sections –1 and ±2 verified the supplementary theorems to the extent of the table.

[edit] History and alternate statements

There are a number of ways to state the theorem. Keep in mind that Euler and Legendre did not have Gauss's congruence notation, nor did Gauss have the Legendre symbol.

 In this article p and q always refer to distinct positive odd primes.

[edit] Fermat

Fermat proved[4] (or claimed to have proved)[5] a number of theorems about expressing a prime by a quadratic form:

p=x^2+\;\,y^2\mbox{ if and only if } p=2 \mbox{ or } p\equiv 1 \pmod4
p=x^2+2y^2\mbox{ if and only if } p=2 \mbox{ or } p\equiv 1, 3 \pmod8
p=x^2+3y^2\mbox{ if and only if } p=3 \mbox{ or } p\equiv 1 \pmod3

He did not state the law of quadratic reciprocity, although the cases –1, ±2, and ±3 are easy deductions from these and other of his theorems.

He also claimed to have a proof that if the prime number p ends with 7, and the prime number q ends in 3, (in base 10), then

pq = x2 + 5x2.

Euler conjectured, and Lagrange proved, that[6]

\mbox{If }\;\,p \equiv 1, 9, \pmod{ 20 }\mbox{ then }\;\,p = x^2+5y^2
\mbox{If }p, q \equiv 3, 7 \pmod{ 20 }\mbox{ then } pq=x^2+5y^2.

Proving these and other statements of Fermat was one of the things that led mathematicians to the reciprocity theorem.

[edit] Euler

Translated into modern notation, Euler stated:[7]

1) If q ≡ 1 (mod 4) then q is a quadratic residue (mod p) if and only if p ≡ r (mod q), where r is a quadratic residue of q.

2) If q ≡ 3 (mod 4) then q is a quadratic residue (mod p) if and only if p ≡ ±b2 (mod 4q), where b is odd and not divisible by q.

He proved[8] the supplementary law for 2.

[edit] Legendre and his symbol

Legendre[9] lets a and A represent positive primes ≡ 1 (mod 4) and b and B positive primes ≡ 3 (mod 4), and sets out a table of eight theorems that together are equivalent to quadratic reciprocity:

Théorème Si il s'ensuit
I b^\frac{a-1}{2}\equiv +1 \pmod a a^\frac{b-1}{2}\equiv +1 \pmod b
II a^\frac{b-1}{2}\equiv -1 \pmod b b^\frac{a-1}{2}\equiv -1 \pmod a
III a^\frac{A-1}{2}\equiv +1 \pmod A A^\frac{a-1}{2}\equiv +1 \pmod a
IV a^\frac{A-1}{2}\equiv -1 \pmod A A^\frac{a-1}{2}\equiv -1 \pmod a
V a^\frac{b-1}{2}\equiv +1 \pmod b b^\frac{a-1}{2}\equiv +1 \pmod a
VI b^\frac{a-1}{2}\equiv -1 \pmod a a^\frac{b-1}{2}\equiv -1 \pmod b
VII b^\frac{B-1}{2}\equiv +1 \pmod B B^\frac{b-1}{2}\equiv -1 \pmod b
VIII b^\frac{B-1}{2}\equiv -1 \pmod B B^\frac{b-1}{2}\equiv +1 \pmod b


He says that since expressions of the form N^\frac{c-1}{2}\pmod c will come up so often, he will abbreviate it (where it is understood gcd(N, c) = 1):

\left(\frac{N}{c}\right) = \pm 1 \equiv N^\frac{c-1}{2} \pmod c

This is now known as the Legendre symbol, and an equivalent[10][11] definition is used today: for all integers a and all odd primes p

\left(\frac{a}{p}\right) = \begin{cases} \;\;\,0\mbox{ if } a \equiv 0 \pmod{p} \\+1\mbox{ if }a \not\equiv 0\pmod{p} \mbox{ and for some integer }x, \;a\equiv x^2\pmod{p} \\-1\mbox{ if there is no such } x. \end{cases}

[edit] Legendre's version of quadratic reciprocity

\left(\frac{p}{q}\right) = \begin{cases} +\left(\frac{q}{p}\right)\mbox{ if }p\equiv 1 \pmod{4} \mbox{ or } q \equiv 1 \pmod{4} \\-\left(\frac{q}{p}\right)\mbox{ if } p\equiv q \equiv 3 \pmod{4} \end{cases}

He notes that these can be combined:

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

A number of proofs, especially those based on Gauss's Lemma,[12] explicitly calculate this formula.

[edit] The supplementary laws using Legendre symbols

\left(\frac{-1}{p}\right) = (-1)^{\frac{(p-1)}{2}} = \left\{\begin{array}{cl} 1 & \textrm{if}\;p \equiv 1 \pmod 4\\ -1 &\textrm{if}\;p \equiv 3 \pmod 4\end{array}\right.
{\left(\frac{2}{p}\right) = (-1)^{\frac{(p^2-1)}{8}} = \left\{\begin{array}{cl} 1 & \textrm{if}\;p \equiv 1\;\textrm{ or }\;7 \pmod 8\\ -1 &\textrm{if}\;p \equiv 3\;\textrm{ or }\;5\pmod 8\end{array}\right.}

Legendre's attempt to prove reciprocity is based on a theorem of his:

Let a,b, and c be integers that satisfy

gcd(a,b) = gcd(b,c) = gcd(c,a) = 1.
At least one of ab,bc,ca < 0.
u^2 \equiv -bc \pmod a,\; v^2 \equiv -ca \pmod b, \mbox{ and } w^2 \equiv -ab \pmod c \mbox{ are solvable.}

Then the equation ax2 + by2 + cz2 = 0 has a nontrivial solution in integers.

E.g., Théorème I is handled by letting a ≡ 1 and b ≡ 3 (mod 4) be primes and assuming that (\tfrac{b}{a}) = 1 and, contrary the theorem, that (\tfrac{a}{b}) = -1. Then x2 + ay2 − bz2 = 0 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 (\tfrac{B}{b}) = (\tfrac{b}{B}) = -1. Then if there is another prime p ≡ 1 (mod 4) such that (\tfrac{p}{b}) =(\tfrac{p}{B}) = -1, the solvability of Bx2 + by2 − pz2 = 0 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":

\mbox{If }a \equiv 1 \pmod4 \mbox{ is prime there exists a prime } \beta \mbox{ such that }\left(\frac{a}{\beta}\right)=-1,

but he couldn't prove that either. Hilbert symbol (below) discusses how techniques based on the existence of solutions to ax2 + by2 + cz2 = 0 can be made to work.

[edit] Gauss

Part of Article 131 in the first edition (1801) of the Disquisitiones, listing the 8 cases of quadratic reciprocity
Part of Article 131 in the first edition (1801) of the Disquisitiones, listing the 8 cases of quadratic reciprocity

Gauss first proves[13] the supplementary laws. He sets[14] the basis for induction by proving the theorem for ±3 and ±5. Noting[15] that it is easier to state for –3 and +5 than it is for +3 or –5, he states[16] the general theorem in the form:

If p is a prime of the form 4n+1 then p, but if p is of the form 4n+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:

Case If Then
1) ±a R a′ ±a′ R a
2) ±a N a′ ±a′ N a
3) +a R b
–a N b		 ±b R a
4) +a N b
–a R b		 ±b N a
5) ±b R a +a R b
–a N b
6) ±b N a +a N b
–a R b
7) +b R b′
–b N b′		 –b′ N b
+b′ R b
8) –b N b′
+b R b′		 +b′ R b
–b′ N b

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

Case If Then
9) ±a R A ±A R a
10) ±b R A +A R b
–A N b
11) +a R B ±B R a
12) –a R B ±B N a
13) +b R B –B N b
+N R b
14) –b R B +B R b
–B N b

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,[17] a lemma similar to the one Legendre needed: \mbox{If }p \equiv 1 \pmod 8 \mbox{ is prime, then there exists an odd prime }q <2\sqrt p+1 \mbox{ such that }\left(\frac{p}{q}\right) = -1.

The proof[18] 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).

[edit] Gauss's version in Legendre symbols

\left(\frac{p}{q}\right) = \begin{cases} \left(\frac{q}{p}\right) \;\;\mbox{ if } q \equiv 1 \pmod{4} \\\left(\frac{-q}{p}\right) \mbox{ if } q \equiv 3 \pmod{4} \end{cases}


These can be combined:

\mbox{Let } q^* = (-1)^\frac{q-1}{2}q, \mbox{ (In other words } |q^*|=|q| \mbox{ and }q^*\equiv 1 \pmod 4. \mbox{)}
\mbox{ Then } \left(\frac{p}{q}\right) = \left(\frac{q^*}{p}\right)


A number of proofs of the theorem, especially those based on Gauss sums,[19] or the splitting of primes in algebraic number fields,[20] derive this formula.

[edit] Other statements

[edit] Euler

This form of quadratic reciprocity is derived from Euler's work:[21]

\mbox{If }p \equiv \pm q \pmod {4a} \mbox{ then } \left(\frac{a}{p}\right) =\left(\frac{a}{q}\right).

[edit] Gauss

Gauss's fourth proof[22] 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.

[edit] Eisenstein

Eisenstein[23] put it like this:

\mbox{If } p\ne q, p'\ne q', p \equiv p' \pmod 4, \mbox{ and } q \equiv q' \pmod 4\mbox{ then } \Bigg(\frac{p}{q}\Bigg) \left(\frac{q}{p}\right) =\left(\frac{p'}{q'}\right) \left(\frac{q'}{p'}\right)

[edit] Mordell

Mordell[24] proved that this is equivalent to quadratic reciprocity:

Let a,b, and c be integers. Then for every prime p that divides abc,
\mbox{if }ax^2 + by^2 + cz^2 \equiv 0 \pmod{4abc/p} \mbox{ has a nontrivial solution }
\mbox{so does }ax^2 + by^2 + cz^2 \equiv 0 \pmod{4abc}.

[edit] Jacobi symbol

The Jacobi symbol is 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

\left(\frac{-1}{n}\right) = (-1)^{\frac{(n-1)}{2}} = \left\{\begin{array}{cl} 1 & \textrm{if}\;n \equiv 1 \pmod 4\\ -1 &\textrm{if}\;n \equiv 3 \pmod 4\end{array}\right.
{\left(\frac{2}{n}\right) = (-1)^{\frac{(n^2-1)}{8}} = \left\{\begin{array}{cl} 1 & \textrm{if}\;n \equiv 1\;\textrm{ or }\;7 \pmod 8\\ -1 &\textrm{if}\;n \equiv 3\;\textrm{ or }\;5\pmod 8\end{array}\right.}

and if both numbers are positive and odd (this is sometimes called "Jacobi's reciprocity law"):

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


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:

\left(\frac{M}{p}\right) = (-1)^{(p-1)(M-1)/4} \Bigg(\frac{p}{M}\Bigg) ,

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

\left(\frac{a}{m}\right) =\left(\frac{a}{m \pm 4an}\right)\mbox{ where }n \mbox{ is an integer and } m\pm4an>0.

For example, (\tfrac{2}{7}) =(\tfrac{2}{15}) =(\tfrac{2}{23}) =(\tfrac{2}{31}) \dots=1, 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 (\tfrac{a}{m}) = -1, we know that a is a nonresidue modulo every prime in the arithmetic series m + 4a, m + 8a, ..., if there are any primes in this series, but that wasn't proved until decades[25] after Legendre.

Eisenstein's formula requires relative primality conditions (which are true if the numbers are prime)

If a,b,a' and b' are positive and odd and gcd(a,b) = gcd(a',b') = 1, then

\mbox{if } a \equiv a' \pmod 4 \mbox{ and } b \equiv b' \pmod 4,\; \Bigg(\frac{a}{b}\Bigg) \left(\frac{b}{a}\right) =\left(\frac{a'}{b'}\right) \left(\frac{b'}{a'}\right).

[edit] Hilbert symbol

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. It is defined to be 1 if and only if the equation ax2 + by2 = z2 has a solution in the completion of the rationals at v other than x = y = z = 0. 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 extension can rightly be considered a generalization of quadratic reciprocity to all global fields.

[edit] Generalizations

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[26] paper he proves a number of theorems, the most important being that if p ≡ 1 (mod 4) then x4 ≡ 2 (mod p) has a solution if and only if p = a2 + 64b2 where a and b are integers.

If p ≡ 3 (mod 4) then every quadratic residue (mod p) is also a biquadratic residue. If r ≡ x2 (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[27] 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 + 2i)(3 – 2i)), 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,[28] and he notes that cubic reciprocity is 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.[29]

Lemmermeyer's Reciprocity Laws (in the references), covers all of this and much more.

[edit] See also

[edit] Notes

  1. ^ Gauss, DA § 4, arts 107-150
  2. ^ E.g. in his mathematical diary entry for April 8, 1796 (the date he first proved quadratic reciprocity). See facsilile page from Felix Klein's Development of Mathematics in the 19th Century
  3. ^ See F. Lemmermeyer's chronology and bibliography of proofs in the external references
  4. ^ Lemmermeyer, pp. 2-3
  5. ^ Gauss, DA, art. 182
  6. ^ Lemmermeyer, p. 3
  7. ^ Lemmermeyer, p. 5, Ireland & Rosen, p 54, 61
  8. ^ Ireland & Rosen, pp. 69-70. His proof is based on what are now called Gauss sums.
  9. ^ This section is based on Lemmermeyer, pp. 6-8
  10. ^ The equivalence is Euler's criterion
  11. ^ The analogue of Legendre's original definition is used for higher-power residue symbols
  12. ^ E.g. Kronecker's proof (Lemmermeyer, ex. p. 31, 1.34) is to use Gauss's lemma to establish that
    \left(\frac{p}{q}\right) =\sgn\prod_{i=1}^{\frac{q-1}{2}}\prod_{k=1}^{\frac{p-1}{2}}\left(\frac{k}{p}-\frac{i}{q}\right)
    and then switch p and q.
  13. ^ Gauss, DA, arts 108-116
  14. ^ Gauss, DA, arts 117-123
  15. ^ Gauss, DA, arts 130
  16. ^ Gauss, DA, Art 131
  17. ^ Gauss, DA, arts. 125-129
  18. ^ Gauss, DA, arts 135-144
  19. ^ Because the basic Gauss sum equals \sqrt{q^*}.
  20. ^ Because the quadratic field Q(\sqrt{q^*}) is a subfield of the cyclotomic field Q(e^\frac{2\pi i}{q})
  21. ^ Ireland & Rosen, p 60-61.
  22. ^ Gauss, "Summierung gewisser Reihen von besonderer Art", reprinted in Untersuchumgen uber hohere Arithmetik, pp.463-495
  23. ^ Lemmermeyer, Th. 2.28, pp 63-65
  24. ^ Lemmermeyer, ex. 1.9, p. 28
  25. ^ By Dirichlet in 1837
  26. ^ C. F. Gauss, Theorie der biquadratischen Reste, Comm. Soc. Reg. Sci. Gottingen (1828); reprinted in Untersuchungen uber hohere Arithmetik, pp. 511-533
  27. ^ 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
  28. ^ He doesn't prove it in this paper, and never published the third installment; it was first proven by Eisenstein.
  29. ^ 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

[edit] References

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.

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[1] says it all:

Count the number of proofs to the law of quadratic reciprocity given thus far in this book and devise another one.

  • Gauss, Carl Friedrich & Clarke, Arthur A. (translator into English) (1986), Disquisitiones Arithemeticae (Second, corrected edition), New York: Springer, ISBN 0387962549 
  • Gauss, Carl Friedrich & Maser, H. (translator into German) (1965), Untersuchungen uber hohere Arithmetik (Disquisitiones Arithemeticae & other papers on number theory) (Second edition), New York: Chelsea, ISBN 0-8284-0191-8 
  • Ireland, Kenneth & Rosen, Michael (1990), A Classical Introduction to Modern Number Theory (second edition), New York: Springer, ISBN 0-387-97329-X 

[edit] External links