nLab
quadratic reciprocity law

Contents

Contents

Idea

In number theory, the quadratic reciprocity law determines a precise relationship between the truth of pRqp R q and the truth of qRpq R p, where pRqp R q is this binary relation on odd prime numbers: “pp is a square modulo qq”.

The law of quadratic reciprocity is a celebrated result due to Gauss; the ideas required to prove it helped to inaugurate modern number theory. It is today largely considered within the context of class field theory, involving how primes decompose in abelian extensions of number fields.

Statement

For p1p \geq 1 an odd prime number, and for any integer aa, define the Legendre symbol (or quadratic reciprocity symbol) (ap)\left(\frac{a}{p}\right) to be the unique element in {1,0,1}\{-1, 0, 1\} for which

(ap)a p12modp \left(\frac{a}{p}\right) \equiv a^{\frac{p-1}{2}} \; mod \; p

Notice that the Legendre symbol defines a surjective homomorphism on a cyclic group

(/p) *C p1{1,1}(\mathbb{Z}/p)^\ast \cong C_{p-1} \to \{-1, 1\}

whose kernel is the set of squares in the multiplicative group (/p) *(\mathbb{Z}/p)^\ast, so that (ap)=1\left(\frac{a}{p}\right) = 1 means aa is a square modulo pp, and (ap)=1\left(\frac{a}{p}\right) = -1 means aa is a non-square modulo pp.

Theorem (Quadratic Reciprocity)

For pp, qq distinct odd primes,

(pq)(qp)=(1) p12q12.\left(\frac{p}{q}\right) \left(\frac{q}{p}\right) = (-1)^{\frac{p-1}{2}\frac{q-1}{2}}.
\,
(2p)=(1) p 218\left(\frac{2}{p}\right) = (-1)^{\frac{p^2-1}{8}}

i.e., 22 is a square modulo pp if and only if p±1mod8p \equiv \pm 1 \; mod \; 8.

The case for odd primes pp, qq can be restated as:

  • if p,qp,q are odd and p1mod4p \equiv 1 \; mod \; 4, then (pq)=(qp)\left(\frac{p}{q}\right) = \left(\frac{q}{p}\right)

  • if p,q3mod4p,q \equiv 3 \; mod \; 4 then (pq)=(qp)\left(\frac{p}{q}\right) = -\left(\frac{q}{p}\right)

The law of quadratic reciprocity was first fully proven by Gauss, although special cases were proven by Fermat (who effectively realized when 1-1 was a square modulo pp based on his two squares theorem? – well before Legendre introduced his eponymous symbol), and Euler (who proved the case for q=2q = 2).

None of these early authors were in full possession of modern notations such as the congruence symbol or the Legendre symbol, which greatly economize the amount of thought needed to prove this theorem. Recognition of quadratic reciprocity was likely rooted in empirical observations, for example the study of periods of expansions of 1/q1/q in base pp (source?).

Sample classroom application

Consider the problem of computing the length of the period of 1/655371/65537 in its decimal expansion. This period is the same as the least positive exponent nn such that 10 n1mod6553710^n \equiv 1 \; mod \; 65537, and is a divisor of 6553665536 (thus, a power of 22). Indeed, 6553765537 is a Fermat prime: 2 2 4+12^{2^4} + 1.

The period is a proper divisor of 6553665536 if and only if 1010 is a square modulo p=65537p = 65537, leading one to contemplate

(10p)=(2p)(5p)\left(\frac{10}{p}\right) = \left(\frac{2}{p}\right) \left(\frac{5}{p}\right)

where the first factor is pretty clearly 11 (already 2 321modp2^{32} \equiv 1 \; mod \; p, so certainly 2 p121modp2^{\frac{p-1}{2}} \equiv 1 \; mod \; p). The other factor is

(5p)=(p5)=(25)=1\left(\frac{5}{p}\right) = \left(\frac{p}{5}\right) = \left(\frac{2}{5}\right) = -1

and we therefore conclude 1010 is a non-square modulo 6553765537, or in other words that the length of the period of 1/655371/65537 is 6553665536.

Proofs

There are today several hundred published proofs of the quadratic reciprocity laws; it is rightly regarded as a capstone result in introductions to number theory. We give two proofs here.

Proof via Gauss sums

This proof, following Lang (pp. 76–78), is middling in sophistication but at least indicates the relevance of cyclotomic extensions of the rationals \mathbb{Q} and quadratic extension?s therein. Let pp be a fixed odd prime, and let ζ\zeta be a primitive p thp^{th} root of unity. Using the Legendre symbol, we introduce a particular character sum called a Gauss sum?,

S a(ap)ζ a,S \coloneqq \sum_a \left(\frac{a}{p}\right) \zeta^a,

where the sum is over non-zero elements aa of /p\mathbb{Z}/p.

Lemma

S 2=(1p)pS^2 = \left(\frac{-1}{p}\right) p.

Proof

We have S 2= a,b(abp)ζ a+bS^2 = \sum_{a, b} \left(\frac{a b}{p}\right) \zeta^{a + b}. For any fixed non-zero aa, as bb ranges over all non-zero residue classes, so does aba b. We may therefore replace bb by aba b to get

S 2 = a,b(a 2bp)ζ a+ab = a,b(bp)ζ a(1+b) = a(1p)ζ 0+ b1(bp) aζ a(1+b).\array{ S^2 & = & \sum_{a, b} \left(\frac{a^2 b}{p}\right) \zeta^{a + a b} \\ & = & \sum_{a, b} \left(\frac{b}{p}\right) \zeta^{a(1 + b)} \\ & = & \sum_a \left(\frac{-1}{p}\right) \zeta^0 + \sum_{b \neq -1} \left(\frac{b}{p}\right) \sum_a \zeta^{a(1 + b)} }.

Now, for b1b \neq -1, the character sum aζ a(1+b)\sum_a \zeta^{a(1+b)} evaluates to 1-1 since 1+ζ++ζ p1=01 + \zeta + \ldots + \zeta^{p-1} = 0. Thus the calculation continues:

S 2 = (1p)(p1)+(1) b1(bp) = (1p)p b(bp) = (1p)p\array{ S^2 & = & \left(\frac{-1}{p}\right) (p-1) + (-1)\sum_{b \neq -1} \left(\frac{b}{p}\right) \\ & = & \left(\frac{-1}{p}\right) p - \sum_b \left(\frac{b}{p}\right) \\ & = & \left(\frac{-1}{p}\right) p }

which completes the proof.

Thus SS belongs to a quadratic extension of \mathbb{Q}, either (p)\mathbb{Q}(\sqrt{p}) or (p)\mathbb{Q}(\sqrt{-p}) depending on the Legendre symbol. In particular, the prime pp is ramified in (ζ)\mathbb{Q}(\zeta).

Proof of quadratic reciprocity law

First let pp, qq be two distinct odd primes. With SS defined as above, we calculate S qmodqS^q \; mod \; q, where modqmod \; q indicates the quotient of the ideal generated by qq in the above-mentioned quadratic extension of \mathbb{Q}, in two ways.

On the one hand, by the preceding lemma,

S q = S(S 2) q12 = S(1p) q12p q12 = S(1) p12q12p q12 S(1) p12q12(pq)modq.\array{ S^q & = & S(S^2)^{\frac{q-1}{2}} \\ & = & S\left(\frac{-1}{p}\right)^{\frac{q-1}{2}} p^{\frac{q-1}{2}} \\ & = & S(-1)^{\frac{p-1}{2}\frac{q-1}{2}} p^{\frac{q-1}{2}} \\ & \equiv & S (-1)^{\frac{p-1}{2}\frac{q-1}{2}} \left(\frac{p}{q}\right) \; mod \; q .}

On the other hand, since raising to the power qq is an automorphism on the quotient ring obtained modulo qq (either 𝔽 q×𝔽 q\mathbb{F}_q \times \mathbb{F}_q or 𝔽 q 2\mathbb{F}_{q^2}, depending on whether pp is a square modulo qq or not), we have

S q a(ap)ζ aqmodq (qp) a(aqp)ζ aqmodq (qp)Smodq\array{ S^q & \equiv & \sum_a \left(\frac{a}{p}\right) \zeta^{a q} \; mod \; q \\ & \equiv & \left(\frac{q}{p}\right) \sum_a \left(\frac{a q}{p}\right) \zeta^{a q} \; mod \; q \\ & \equiv & \left(\frac{q}{p}\right) S \; mod \; q }

and now we can cancel SS (which is invertible modulo qq, since S 2S^2 is) to arrive at

(qp)=(1) p12q12(pq)\left(\frac{q}{p}\right) = (-1)^{\frac{p-1}{2}\frac{q-1}{2}} \left(\frac{p}{q}\right)

which gives the first clause of the reciprocity law.

As for the second clause, we can give a similar analysis. The prime q=2q = 2 is ramified in the cyclotomic extension [i]\mathbb{Q}[i] since (1+i) 2=2i(1 + i)^2 = 2 i, and for any prime pp we may calculate (1+i) pmodp(1 + i)^p \; mod \; p in two ways. On the one hand,

(1+i) p = (1+i)(2i) p12 (1+i)i p12(2p)modp\array{ (1 + i)^p & = & (1+i)(2 i)^{\frac{p-1}{2}} \\ & \equiv & (1+i)i^{\frac{p-1}{2}} \left(\frac{2}{p}\right) \; mod \; p }

and on the other hand,

(1+i) p 1 p+i pmodp\array{ (1+i)^p & \equiv & 1^p + i^p \; mod \; p }

and by examining the cases p1,3,5,7mod8p \equiv 1, 3, 5, 7 \; mod \; 8 separately, we easily deduce the second clause.

Zolotarev’s proof

The (in hindsight obvious!) structural meaning of the Legendre symbol was first given by Zolotarev:

Lemma (Zolotarev)

For pp an odd prime and aa relatively prime to pp, (ap)\left(\frac{a}{p}\right) is the sign or signature of a permutation on (/p) *(\mathbb{Z}/p)^\ast given by multiplying by aa.

Proof

Both the Legendre symbol (p):(/p) *{1,1}\left(\frac{ }{p}\right) \colon (\mathbb{Z}/p)^\ast \to \{-1, 1\} and

(/p) *CayleyPerm((/p) *)sign{1,1}(\mathbb{Z}/p)^\ast \stackrel{Cayley}{\to} Perm((\mathbb{Z}/p)^\ast) \stackrel{sign}{\to} \{-1, 1\}

are homomorphisms whose domain is a cyclic group, so it suffices to show they agree on a generator gg. But Cayley(g)Cayley(g) is a cyclic permutation on p1p-1 elements, hence has sign (1) p2=1(-1)^{p-2} = -1, which agrees with (gp)\left(\frac{g}{p}\right).

We turn now to Zolotarev’s proof of the “hard” case of quadratic reciprocity where pp and qq are distinct odd primes. What is interesting is that from this point forward, we don’t use primality of pp and qq at all, i.e., the remainder of the argument carries over if pp and qq are replaced by odd, relatively prime integers mm and nn, and we simply define (an)\left(\frac{a}{n}\right) as a sign of a permutation of multiplying by aa on (/n) *(\mathbb{Z}/n)^\ast. Indeed, one often defines the Jacobi symbol by

(an) i(ap i)\left(\frac{a}{n}\right) \coloneqq \prod_{i} \left(\frac{a}{p_i}\right)

where n=p 1p rn = p_1 \ldots p_r is the prime factorization of an odd integer, and what we really do is generalize quadratic reciprocity from the Legendre symbol to the Jacobi symbol. Thus, the primality assumption is concentrated purely in the preceding lemma.

Proof of quadratic reciprocity

For m>1m \gt 1 an odd number, we consider the set /m={0,1,,m1}\mathbb{Z}/m = \{0, 1, \ldots, m-1\} as carrying on the one hand a ring structure, and on the other as carrying a structure of linear order (no compatibility between these structures!). Now suppose mm and nn are odd and relatively prime; then by the Chinese remainder theorem?, there is a unique ring isomorphism

/mn/m×/n.\mathbb{Z}/m n \to \mathbb{Z}/m \times \mathbb{Z}/n.

If we endow /m×/n\mathbb{Z}/m \times \mathbb{Z}/n with the dictionary or lexicographic order, then there is also a unique isomorphism of linear or total orders

(/m×/n) Dict/mn(\mathbb{Z}/m \times \mathbb{Z}/n)_{Dict} \to \mathbb{Z}/m n

which takes an element (x,y)/m×/n(x, y) \in \mathbb{Z}/m \times \mathbb{Z}/n to nx+y{0,1,,mn1}n x + y \in \{0, 1, \ldots, m n - 1\}. (Intuitively, imagine assembling a rectangular array of cards, with mm columns and nn cards in each column, into a single stack of mnm n cards, by gathering up the first column, followed by gathering up the second column and placing it underneath, etc.)

The composite α\alpha of the functions

(/m×/n) Dictord/mnring/m×/n(\mathbb{Z}/m \times \mathbb{Z}/n)_{Dict} \stackrel{ord \cong}{\to} \mathbb{Z}/m n \stackrel{ring \cong}{\to} \mathbb{Z}/m \times \mathbb{Z}/n

is thus (x,y)nx+y(nx+y,y)(x, y) \mapsto n x + y \mapsto (n x + y, y). The composite is thus a juxtaposition of nn row permutations, one for each fixed yy, where xx in row yy is taken to nx+yn x + y in row yy. The sign of such a permutation xnx+yx \mapsto n x + y is

sign(()+y)sign(n())=sign(n())=(nm)sign((-) + y) \cdot sign(n(-)) = sign(n(-)) = \left(\frac{n}{m}\right)

(since the permutation ()+y(-) + y is a cyclic permutation on an odd number of elements, hence is even). Thus

sign(α)=(nm) n=(nm)sign(\alpha) = \left(\frac{n}{m}\right)^n = \left(\frac{n}{m}\right)

where the second equation follows since nn is odd.

Similarly, consider /m×/n\mathbb{Z}/m \times \mathbb{Z}/n with the reverse dictionary order, where (x,y)<(x,y)(x, y) \lt (x', y') if y<yy \lt y' or y=yy = y' and x<xx \lt x'. We again have a unique order isomorphism and unique ring isomorphism, and we can analyze their composition β\beta,

(/m×/n) RevDictord/mnring/m×/n,(\mathbb{Z}/m \times \mathbb{Z}/n)_{RevDict} \stackrel{ord \cong}{\to} \mathbb{Z}/m n \stackrel{ring \cong}{\to} \mathbb{Z}/m \times \mathbb{Z}/n,

as taking (x,y)(x,x+my)(x, y) \mapsto (x, x + m y). We similarly calculate

sign(β)=(mn).sign(\beta) = \left(\frac{m}{n}\right).

Finally, β 1α\beta^{-1} \circ \alpha is the unique order-preserving isomorphism

(/m×/n) Dict(/m×/n) RevDict(\mathbb{Z}/m \times \mathbb{Z}/n)_{Dict} \to (\mathbb{Z}/m \times \mathbb{Z}/n)_{RevDict}

which gives a permutation on the underlying set /m×/n\mathbb{Z}/m \times \mathbb{Z}/n, and it remains to show that its sign is (1) m12n12(-1)^{\frac{m-1}{2}\frac{n-1}{2}}.

But this is easy to see. Recall that given a permutation σ\sigma on a linearly ordered set (such as (/m×/n) Dict(\mathbb{Z}/m \times \mathbb{Z}/n)_{Dict}), an inversion is a pair (x<y)(x \lt y) such that σ(x)>σ(y)\sigma(x) \gt \sigma(y), and if I(σ)I(\sigma) is the total number of inversions, then

sign(σ)=(1) I(σ).\sign(\sigma) = (-1)^{I(\sigma)}.

In the present case σ=β 1α\sigma = \beta^{-1} \alpha, we see I(σ)I(\sigma) counts pairs of pairs (i,j)(i, j), (i,j)(i', j') where (i,j)<(i,j)(i, j) \lt (i', j') in dictionary order but (i,j)>(i,j)(i, j) \gt (i', j') in reverse dictionary order; in other words when i<ii \lt i' but j<jj' \lt j. The number of such occurrences is

I(σ)=m(m1)2n(n1)2I(\sigma) = \frac{m(m-1)}{2} \frac{n(n-1)}{2}

whence (again since m,nm, n are odd)

(1) I(σ)=(1) m12n12(-1)^{I(\sigma)} = (-1)^{\frac{m-1}{2}\frac{n-1}{2}}

which completes the proof.

Other reciprocity laws

As mentioned earlier, quadratic reciprocity law is due to Gauss and is the first of a number of reciprocity laws in number theory. The Wikipedia article lists a bevy of reciprocity laws, gradually increasing in modernity and abstraction (and power), and culminating in Artin reciprocity, a capstone of the classical class field theory.

References

  • Carl Friedrich Gauss, Disquisitiones arithmeticae (1801), Article IV.

  • E.I. Zolotareff, Nouvelle démonstration de la loi de de réciprocité de Legendre, Nouvelles Annales de Mathématiques. 2e série 11 (1872) 354–362.

Last revised on March 29, 2017 at 09:34:23. See the history of this page for a list of all contributions to it.