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$\left(\frac{p}{q}\right)\left(\frac{q}{p}\right)={(-1)}^{ab}$.

($\left(\frac{v}{w}\right)$ is the Legendre symbol.)

Proof:Let $R$ be the subset $[-a,a]\times [-b,b]$of $\mathbb{Z}\times \mathbb{Z}$. Let $S$be the interval

$$[-(pq-1)/2,(pq-1)/2]$$

of $\mathbb{Z}$.By the Chinese remainder theorem, there exists a uniquebijection $f:S\to R$ such that, for any $s\in S$, if wewrite $f(s)=(x,y)$, then$x\equiv s(modp)$ and$y\equiv s(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 , and $v$ elements of the form$(0,y)$ with . Intending to apply Gauss’s lemma,we seek some kind of comparison between $u$ and $v$.

We define three subsets of $P$ by

$R_0$$=$$\mathrm{\{}(x,y)\in P|x>0,y>0\}$

$R_1$$=$

$R_2$$=$

and we let $N_i$ be the cardinal of $R_i$ 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$1\le k\le b$ and $0\le l\le a$.Thus

$$N_0+N_1=ab+b-(b-v)+u$$

i.e.

$N_0+N_1$$=$$ab+u+v.$(1)

Swapping $p$ and $q$, we have likewise

$N_0+N_2$$=$$ab+u+v.$(2)

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

$N_1+N_2$$=$$ab+u+v.$(3)

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

$$0\equiv ab+u+v(mod2)$$

so

$${(-1)}^{ab}={(-1)}^u{(-1)}^v$$

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

For a bibliography of the more than 200 known proofs ofthe QRL, seehttp://www.rzuser.uni-heidelberg.de/ hb3/fchrono.htmlLemmermeyer.