= Lattice-point count for quadratic reciprocity
{title2=$M+N=(p-1)(q-1)/4$}
A short proof outline connects <Gauss's lemma (number theory)> to counting points with <integer> coordinates. For distinct <odd primes> $p,q$, define the two <floor function> sums
$$
M=\sum_{i=1}^{(p-1)/2}\left\lfloor\frac{qi}{p}\right\rfloor,\qquad
N=\sum_{j=1}^{(q-1)/2}\left\lfloor\frac{pj}{q}\right\rfloor.
$$
The parity form of <Gauss's lemma (number theory)> gives $(q/p)=(-1)^M$ and $(p/q)=(-1)^N$. In the open <rectangle> $0<x<p/2$, $0<y<q/2$, the <line> $y=qx/p$ separates $M$ points below it from $N$ points above it. None lies on the <line>, because $py=qx$ and <coprimality> would force $p\mid x$. The total is therefore $(p-1)(q-1)/4$. Combining that count with the parity identities gives <quadratic reciprocity>.<Quadratic Reciprocity by Ben Lynn>[Ben Lynn, Quadratic Reciprocity, first theorem and proof of the Law of Quadratic Reciprocity: floor-sum parity and the separating-line count]{ref}
\Image[/quadratic-reciprocity-lattice-parity-count.png]
{title=A <line> partitions the <integer> coordinate points behind the <quadratic reciprocity> exponent}
{description=For $p=3,q=7$, the counts are $M=2,N=1$; for $p=5,q=7$, they are $M=N=3$. Dashed edges mark the excluded boundary of the <rectangle>. This illustrates the counting step; the separate parity step from <Gauss's lemma (number theory)> is essential to relate the count to <Legendre symbols>.}
Back to article page
