Proof of the Main Law of Quadratic Reciprocity

proofquadratic-reciprocity

Main Law

For distinct odd primes $p$ and $q$,

$$\begin{array}{rl}\left(\frac{q}{p}\right)& =\{\begin{array}{ll}\left(\frac{p}{q}\right)& \text{ if p or q is 1mod4}\\ -\left(\frac{p}{q}\right)& \text{ if p and q is 3mod4}\end{array}\\ & =(-1{)}^{\frac{p-1}{2}\frac{q-1}{2}}\left(\frac{p}{q}\right).\end{array}$$

Proof

Try to count $\#\{(x_1,\dots ,x_n)\in \mathbb{Z}/p:x_1^2+\dots +x_n^2\equiv 1\mathrm{mod}p\}$

$n=1$

$\#\{x\mathrm{mod}p:x^2\equiv 1\mathrm{mod}p\}=2$

$n=2$

$\#\{(x,y)\mathrm{mod}p:x^2+y^2\equiv 1\mathrm{mod}p\}=??$

$$\begin{array}{cccccccccccc}p& 3& 5& 7& 11& 13& 17& 19& 23& 29& 31& 37\\ \text{count}& 4& 4& 8& 12& 12& 16& 20& 24& 28& 32& 36\end{array}$$

$\text{count}\to p\pm 1$ $p+1:3,7,11,19,23,31$ $p-1:5,13,17,29,37$

Theorem (Stronger)

For $c\not\equiv 0\mathrm{mod}p$, $\#\{(x,y)\mathrm{mod}p:x^2+y^2\equiv c\mathrm{mod}p\}$ is independent of $c$ and in fact is $p-\left(\frac{-1}{p}\right)$.

Proof

Observe that $\#\{x\mathrm{mod}p:x^2\equiv c\mathrm{mod}p\}=1+\left(\frac{c}{p}\right)$. So using this,

$$\begin{array}{rl}\#\{(x,y)\mathrm{mod}p:x^2+y^2\equiv c\mathrm{mod}p\}& =\sum _{\underset{a+b\equiv c\mathrm{mod}p}{(a,b)\mathrm{mod}p}}\#\{x^2\equiv a\mathrm{mod}p\}\cdot \{y^2\equiv b\mathrm{mod}p\}\\ & =\sum _{a+b\equiv c\mathrm{mod}p}\left(1+\left(\frac{a}{p}\right)\right)\cdot \left(1+\left(\frac{b}{p}\right)\right)\\ & =\sum _{a+b\equiv c\mathrm{mod}p}\left(1+\left(\frac{a}{p}\right)+\left(\frac{b}{p}\right)+\left(\frac{ab}{p}\right)\right)\\ & =\sum _{a\mathrm{mod}p}\left(1+\left(\frac{a}{p}\right)+\left(\frac{c-a}{p}\right)+\left(\frac{a(c-a)}{p}\right)\right)\\ & =\sum _{a}1+\sum _a\left(\frac{a}{p}\right)+\sum _a\left(\frac{c-a}{p}\right)+\sum _a\left(\frac{a(c-a)}{p}\right)\\ & =\sum _{a}1+0+0+\sum _a\left(\frac{a(c-a)}{p}\right)\\ & =p+\sum _{a\mathrm{mod}p}\left(\frac{a(c-a)}{p}\right)\to \text{ indep. of c if c≡0modp??}\\ & =p+\sum _{a\mathrm{mod}p}\left(\frac{ca(c-ca)}{p}\right)\text{ change of variables a→camodp for c≡0modp}\\ & =p+\sum _{a\mathrm{mod}p}\left(\frac{c^{2}a(1-a)}{p}\right)\\ & =vp+\sum _{a\mathrm{mod}p}\left(\frac{c^2}{p}\right)\left(\frac{a(1-a)}{p}\right),c\not\equiv 0\mathrm{mod}p\\ & =p+\sum _{a\mathrm{mod}p}\left(\frac{a(1-a)}{p}\right)\to \text{ indep. of c}.\end{array}$$

Why is it $p-\left(\frac{-1}{p}\right)$?

Let $N(c)=\#\{(x,y)\mathrm{mod}p:x^2+y^2\equiv c\mathrm{mod}p\}$, So $N(0)+N(1)+N(2)+\dots +N(p-1)=p^2$ Note that $N(1),N(2),\dots ,N(p-1)$ all have same value. Thus $N(0)+(p-1)N(1)=p^2$ $⟹N(1)=\frac{p^2-N(0)}{p-1},N(0)=\#\{(x,y)\mathrm{mod}p:x^2+y^2\equiv 0\mathrm{mod}p\}$

Note: $x^2+y^2\equiv 0\mathrm{mod}p⟹x^2\equiv -y^2\mathrm{mod}p$, so if $y\not\equiv 0\mathrm{mod}p$ then $(x{y}^{-1}{)}^2\equiv -1\mathrm{mod}p$.

• So if $\left(\frac{-1}{p}\right)=-1$ ($p\equiv 3\mathrm{mod}4$) then the only solution to $x^2+y^2\equiv 0\mathrm{mod}p$ is $(0,0)\mathrm{mod}p:y\equiv 0⟹x\equiv 0$. Then $N(1)=\frac{p^2-1}{p-1}=p+1$. $\star$
• If $\left(\frac{-1}{p}\right)=1$, write $-1\equiv t^2\mathrm{mod}p$. Then $x^2+y^2\equiv 0\mathrm{mod}p⟺x^2\equiv -y^2\mathrm{mod}p⟺x^2\equiv (ty{)}^2\mathrm{mod}p⟺x\equiv \pm ty\mathrm{mod}p$. Therefore, $\{(x,y):x^2+y^2\equiv 0\mathrm{mod}p\}=\{(\pm ty,y):y\in \mathbb{Z}/p\}$, so $\left(\frac{-1}{p}\right)=1⟹N(0)=1+2(p-1)=2p-1⟹N(1)=\frac{p^2-(2p-1)}{p-1}=\frac{p^2-2p+1}{p-1}=\frac{(p-1{)}^2}{p-1}=p-1$. $\star$

Remark

Knowing $\#\{(x,y):x^2+y^2\equiv 1\mathrm{mod}p\}=p-\left(\frac{-1}{p}\right)$, on LHS, most solutions come in packets of size 8: $(x,y),(-x,y),(x,-y),(-x,-y),(y,x),(-y,x),(y,-x),(-y,-x)\mathrm{mod}p$ which are distinct unless $x\equiv 0\mathrm{mod}p$, $y\equiv 0\mathrm{mod}p$, or $x\equiv y\mathrm{mod}p$. By counting $N(1)\mathrm{mod}8$ we can derive formula for $\left(\frac{2}{p}\right)\to$ see Thm 3.1 .

…