Proof of Law of Quadratic Reciprocity
If
\[p, \; q\]
are distinct odd primes then \[(p/q)(q/p)=(-1)^{(p-1)(q-1)/4}\]
.Proof
Consider the rectangle which has coordinates
\[(0,0), \; (p/2,0), \; (p/2,q/2)\]
and \[(0,q/2)\]
. The number of lattice points inside the rectangle is \[\frac{p-1}{2} \times \frac{q-1}{2}\]
. The line from \[(0,0)\]
to \[(p/2,q/2)\]
has equation \[y=\frac{q}{p}x\]
. Inside the rectangle the are no lattice points on the diagonal because if \[(a,b)\]
is such a point then \[b=\frac{q} \rightarrow p | a{p}a\]
and \[q | b\]
, which forces \[(a,b)\]
outside the rectangle.Labelling the regions in the triangle above and below the diagonal from the origin to
\[(a,b)\]
. For \[0 \lt k \lt \frac{p}{2}\]
the number of lattice points in B lying directly above \[(k,0)\]
is \[int( \frac{q}{p} k)\]
. Hence the total number of lattice points in B is \[\alpha (q,p) = \sum_{k=1}^{(p-1)/2} int(\frac{q}{p}{k})\]
. In the same way the number of lattice points in A is \[\alpha (p,q)\]
.We must have
\[\alpha (q,p)+ \alpha (p, q) = \frac{p-1}{2} \times \frac{q-1}{2}\]
.In terms of Legendre Symbols, using this Equation for Legendre Symbols, we have
\[\begin{equation} \begin{aligned} (p/q)(q/p) &= (-1)^{\alpha (p,q)} \times (-1)^{\alpha (q,p)} \\ &= (-1)^{\alpha (p,q)+ \alpha (q,p)} \\ &= (-1)^{(p-1)(q-1)/4} \end{aligned} \end{equation}\]
