# Quadratic Reciprocity Law

Consider a rectangle in $\mathbb{R}^2$ with vertices $(0,0),(\frac{p}{2},0),(0,\frac{q}{2}),(\frac{p}{2},\frac{q}{2})$.

Let $R$ denote the region enclosed by the rectangle, not including the borders

Let $D:y=(\frac{q}{p})x$ denote the diagonal line of $R$.
Let $T_1,T_2$ denote the lower and upper half of R, resp., as seperated by D.

Observe that:
The number of lattice points in $R$ is equal to $\frac{p-1}{2} . \frac{q-1}{2}$
There's no lattice points in $D$, as $gcd(p,q)=1$
The sum of lattice points in $T_1$ and in $T_2$ is precisely the total number in $R$.

Now, we may use some wisdom to count lattice points in $T_1$.


It's intuitive that on the line $x=k$, there's $[\frac{kq}{p}]$ lattice points, hence there's totally $$\sum_{k=1}^{\frac{p-1}{2}}[\frac{kq}{p}]$$

Similarly, there's $$\sum_{j=1}^{\frac{q-1}{2}}[\frac{jp}{q}]$$ points in $T_2$

Recall that total lattice point is $\frac{p-1}{2} . \frac{q-1}{2}$, and hence
$$\frac{p-1}{2} . \frac{q-1}{2} = \sum_{k=1}^{\frac{p-1}{2}}[\frac{kq}{p}]+\sum_{j=1}^{\frac{q-1}{2}}[\frac{kp}{q}]$$

Then, by Euler's Criterion and Gauss' Lemma, we have $$(\frac{p}{q})(\frac{q}{p}) = (-1)^{\frac{1-p}{2}\frac{1-q}{2}}$$

**Q.E.D.**