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 unique bijection $f:S\to R$ such that, for any $s\in S$ , if we write $f(s)=(x,y)$ , then $x\equiv s\pmod{p}$ and $y\equiv s\pmod{q}$ . 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

$\displaystyle R_{0}$	$\displaystyle=$	$\displaystyle\{(x,y)\in P\|x>0,y>0\}$
$\displaystyle R_{1}$	$\displaystyle=$	$\displaystyle\{(x,y)\in P\|x<0,y\geq 0\}$
$\displaystyle R_{2}$	$\displaystyle=$	$\displaystyle\{(x,y)\in P\|x\geq 0,y<0\}$

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\leq k\leq b$ and $0\leq l\leq a$ . Thus

$N_{0}+N_{1}=ab+b-(b-v)+u$

i.e.

$\displaystyle N_{0}+N_{1}$

$\displaystyle=$

$\displaystyle ab+u+v.$

(1)

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

$\displaystyle N_{0}+N_{2}$

$\displaystyle=$

$\displaystyle 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)$ is in $P$ , but not both. Therefore

$\displaystyle N_{1}+N_{2}$

$\displaystyle=$

$\displaystyle ab+u+v.$

(3)

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

$0\equiv ab+u+v\pmod{2}$

$(-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 of the QRL, see http://www.rzuser.uni-heidelberg.de/ 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