## You are here

Homeproof of quadratic reciprocity rule

## Primary tabs

# 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\;\;(\mathop{{\rm mod}}p)$ and $y\equiv s\;\;(\mathop{{\rm mod}}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\;\;(\mathop{{\rm mod}}2)$ |

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 of the QRL, see Lemmermeyer .

## Mathematics Subject Classification

11A15*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff

## Recent Activity

new question: Prove a formula is part of the Gentzen System by LadyAnne

Mar 30

new question: A problem about Euler's totient function by mbhatia

new problem: Problem: Show that phi(a^n-1), (where phi is the Euler totient function), is divisible by n for any natural number n and any natural number a >1. by mbhatia

new problem: MSC browser just displays "No articles found. Up to ." by jaimeglz

Mar 26

new correction: Misspelled name by DavidSteinsaltz

Mar 21

new correction: underline-typo by Filipe

Mar 19

new correction: cocycle pro cocyle by pahio

Mar 7

new image: plot W(t) = P(waiting time <= t) (2nd attempt) by robert_dodier

new image: expected waiting time by robert_dodier

new image: plot W(t) = P(waiting time <= t) by robert_dodier