PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
sections
Encyclopædia
Papers
Books
Expositions

meta
Requests (200)
Orphanage
Unclass'd
Unproven (490)
Corrections (6)
Classification

talkback
Polls
Forums
Feedback
Bug Reports

downloads
Snapshots
PM Book

information
News
Docs
Wiki
ChangeLog
TODO List
Legalese
About
Owner confidence rating: High Entry average rating: No information on entry rating
[parent] proof of quadratic reciprocity rule (Proof)

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

$\displaystyle [-(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 \vert x > 0, y > 0 \}$  
$\displaystyle R_{1}$ $\displaystyle =$ $\displaystyle \{(x,y) \in P \vert x < 0, y \ge 0 \}$  
$\displaystyle R_{2}$ $\displaystyle =$ $\displaystyle \{(x,y) \in P \vert x \ge 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 \le k \le b$ and $ 0 \le l \le a$. Thus

$\displaystyle 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
$\displaystyle 0 \equiv ab + u + v \pmod 2$
so
$\displaystyle (-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 Lemmermeyer .



"proof of quadratic reciprocity rule" is owned by mathcam. [ owner history (1) ]
(view preamble)

View style:

Keywords:  reciprocity

This object's parent.
Log in to rate this entry.
(view current ratings)

Cross-references: conclusion, region, cardinal, Gauss' lemma, contains, bijection, Chinese remainder theorem, interval, subset, proof, Legendre symbol, primes, odd, Gauss, quadratic reciprocity

This is version 9 of proof of quadratic reciprocity rule, born on 2002-12-14, modified 2003-09-26.
Object id is 3752, canonical name is ProofOfQuadraticReciprocityRule.
Accessed 6747 times total.

Classification:
AMS MSC: 11A15 (Number theory :: Elementary number theory :: Power residues, reciprocity)
Pending Errata and Addenda
None.
[ View all 2 ]
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add example | add (any)