proof of quadratic reciprocity rule

The quadratic reciprocity law is:

Theorem: (Gauss) Let p and q be distinct odd primes, and write p=2a+1 and q=2b+1. Then (pq)(qp)=(-1)ab.

((vw) is the Legendre symbolMathworldPlanetmath.)

Proof: Let R be the subset [-a,a]×[-b,b] of ×. Let S be the interval


of . By the Chinese remainder theoremMathworldPlanetmathPlanetmathPlanetmath, there exists a unique bijection f:SR such that, for any sS, if we write f(s)=(x,y), then xs(modp) and ys(modq). Let P be the subset of R consisting of the values of f on [1,(pq-1)/2]. P contains, say, u elements of the form (x,0) such that x<0, and v elements of the form (0,y) with y<0. Intending to apply Gauss’s lemma, we seek some kind of comparison between u and v.

We define three subsets of P by

R0 = {(x,y)P|x>0,y>0}
R1 = {(x,y)P|x<0,y0}
R2 = {(x,y)P|x0,y<0}

and we let Ni be the cardinal of Ri for each i.

P has ab+b elements in the region y>0, namely f(m) for all m of the form k+lq with 1kb and 0la. Thus



N0+N1 = ab+u+v. (1)

Swapping p and q, we have likewise

N0+N2 = ab+u+v. (2)

Furthermore, for any sS, if f(s)=(x,y) then f(-s)=(-x,-y). It follows that for any (x,y)R other than (0,0), either (x,y) or (-x,-y) is in P, but not both. Therefore

N1+N2 = ab+u+v. (3)

Adding (1), (2), and (3) gives us




which, in view of Gauss’s lemma, is the desired conclusionMathworldPlanetmath.

For a bibliography of the more than 200 known proofs of the QRL, see hb3/fchrono.htmlLemmermeyer .

Title proof of quadratic reciprocity rule
Canonical name ProofOfQuadraticReciprocityRule
Date of creation 2013-03-22 13:16:15
Last modified on 2013-03-22 13:16:15
Owner mathcam (2727)
Last modified by mathcam (2727)
Numerical id 12
Author mathcam (2727)
Entry type Proof
Classification msc 11A15