Eisenstein’s Lattice Point Proof of Quadratic Reciprocity

The law of quadratic reciprocity is one of the central results of classical number theory. Gauss called it the Theorema Aureum, or Golden Theorem. Given two distinct odd primes $p$ and $q$ , it relates the question of whether $q$ is a square modulo $p$ to whether $p$ is a square modulo $q$ . These are questions about different moduli, yet their answers are closely related.

Gauss gave several proofs of the theorem. Eisenstein later found a particularly simple geometric proof, based on Gauss’s third proof, in which the relation between the two primes emerges from counting lattice points in a rectangle.

The Law of Quadratic Reciprocity

The Legendre Symbol: For an odd prime $p$ and an integer $a$ , the Legendre symbol $\left(\frac{a}{p}\right)$ records whether $a$ is a square modulo $p$ . It is defined by

$\displaystyle \left(\frac{a}{p}\right) = \begin{cases} 1, & \text{if } a \text{ is a quadratic residue modulo } p \text{ and } p \nmid a, \\ -1, & \text{if } a \text{ is a nonresidue modulo } p \text{ and } p \nmid a, \\ 0, & \text{if } p \mid a. \end{cases}$

Let $p$ and $q$ be distinct odd primes. The law of quadratic reciprocity relates the two Legendre symbols by

$\displaystyle \left(\frac{q}{p}\right)\left(\frac{p}{q}\right)=(-1)^{\frac{p-1}{2}\frac{q-1}{2}}.$

Since both Legendre symbols are either $1$ or $-1$ , the formula says that they are equal unless both primes are congruent to $3\pmod 4$ , in which case they have opposite signs. Thus,

$\displaystyle \left(\frac{q}{p}\right)= \begin{cases} \phantom{-}\left(\frac{p}{q}\right), & \text{if }p\equiv1\pmod4\text{ or }q\equiv1\pmod4,\\ -\left(\frac{p}{q}\right), & \text{if }p\equiv q\equiv3\pmod4.\end{cases}$

It states a surprising symmetry: whether $q$ is a square modulo $p$ is closely related to whether $p$ is a square modulo $q$ . For example, $7\equiv1\pmod3$ is a square modulo $3$ , whereas $3$ is not a square modulo $7$ . Hence $\left(\frac73\right)=1$ and $\left(\frac37\right)=-1$ , as predicted by the theorem, since both primes are congruent to $3\pmod4$ .

Eisenstein’s proof reduces quadratic reciprocity to counting lattice points. The main idea is to express the Legendre symbol as the sign $(-1)^N$ , where $N$ can be calculated using a sum of floor functions. This sum then counts lattice points in a rectangle lying on one side of the line $py=qx$ . Counting the points on both sides of this line will give the reciprocity law.

We begin with Euler’s criterion, which relates the Legendre symbol to a power modulo $p$ .

Euler’s Criterion. Let $p$ be an odd prime and $a$ an integer not divisible by $p$ . Then

$\displaystyle \left(\frac{a}{p}\right)\equiv a^{\frac{p-1}{2}}\pmod p.$

Since the Legendre symbol is either $1$ or $-1$ , this congruence determines it uniquely. In particular, we can find $\left(\frac{q}{p}\right)$ by understanding the product of the $(p-1)/2$ numbers $q,2q,\ldots,\frac{p-1}{2}q$ modulo $p$ . When these numbers are reduced to representatives between $-(p-1)/2$ and $(p-1)/2$ , their absolute values form a permutation of $1,2,\ldots,(p-1)/2$ . Thus, the Legendre symbol is determined by the number of negative signs that occur. This is Gauss’s lemma.

Eisenstein’s geometric argument expresses the parity of this sign count as a sum of floor functions. The advantage is that each floor function counts integers below a certain bound, allowing the reciprocity law to be proved by a simple lattice-point count.

Eisenstein’s Key Sums

Throughout this section, let $M=\frac{p-1}{2}$ . We will consider two sums.

The first is Eisenstein’s arithmetic sum:

$\displaystyle S_E(q,p)=\sum_{k=1}^{M}\left\lfloor\frac{2qk}{p}\right\rfloor.$

Here, $2k$ runs through the even integers $2,4,6,\ldots,p-1$ .

The second is the geometric sum:

$\displaystyle \lambda(q,p)=\sum_{x=1}^{M}\left\lfloor\frac{qx}{p}\right\rfloor.$

Here, $x$ runs through the integers $1,2,\ldots,\frac{p-1}{2}$ .

We will show that these two sums have the same parity:

$\displaystyle S_E(q,p)\equiv\lambda(q,p)\pmod 2.$

This relation connects the two parts of the proof. The first sum arises naturally from the arithmetic argument using Gauss’s lemma, while the second has a simple geometric interpretation as a count of lattice points.

Eisenstein’s Sum $S_E(q,p)$

Consider the sum

$\displaystyle S_E(q,p)=\sum_{k=1}^{M}\left\lfloor\frac{q(2k)}{p}\right\rfloor.$

Here, $2k$ runs through the even integers $2,4,\ldots,p-1$ . For each such integer $x=2k$ , the quantity $\left\lfloor qx/p\right\rfloor$ counts the positive integers $y$ satisfying $py<qx$ , since $qx/p$ is not an integer. Thus, $S_E(q,p)$ counts the lattice points $(x,y)$ satisfying

$\displaystyle x\in \{2,4,\ldots,p-1\},\qquad 1\le y<\frac{qx}{p}.$

Geometrically, these are the lattice points below the line $py=qx$ , with the horizontal coordinate restricted to even integers between $1$ and $p$ .

The Geometric Sum $\lambda(q,p)$

Now consider

$\displaystyle \lambda(q,p)=\sum_{x=1}^{M}\left\lfloor\frac{qx}{p}\right\rfloor.$

Here, $x$ runs through all integers from $1$ to $M=(p-1)/2$ . As before, each term counts the positive integers $y$ satisfying $py<qx$ . Hence, $\lambda(q,p)$ counts the lattice points satisfying

$\displaystyle 1\le x\le\frac{p-1}{2},\qquad 1\le y<\frac{qx}{p}.$

These are precisely the lattice points strictly inside the triangle with vertices

$\displaystyle (0,0),\qquad \left(\frac p2,0\right),\qquad \left(\frac p2,\frac q2\right),$

whose sloping side lies on the line $py=qx$ .

Unlike $S_E(q,p)$ , which counts points only at even horizontal coordinates, $\lambda(q,p)$ counts all lattice points in a simple triangular region. This makes it more convenient for the geometric proof of quadratic reciprocity.

Eisenstein’s Lemma

The first major step is to show that the arithmetic definition of $\left(\frac{q}{p}\right)$ can be expressed in terms of the parity of $S_{E}(q,p)$ .

Lemma 1 (Eisenstein). Let $p$ and $q$ be distinct odd primes. Then

$\displaystyle \left(\frac{q}{p}\right) \;=\; (-1)^{\,S_{E}(q,p)}.$

Proof: Let $\displaystyle E=\{2,4,6,\dots,p-1\}.$ This is the set of even nonzero residues modulo $p$ . It has $\displaystyle M=\frac{p-1}{2}$ elements. For each $u\in E$ , let $r_u$ be the least positive residue of $q u$ modulo $p$ . Thus $\displaystyle q u \equiv r_u \pmod{p}, 1\le r_u\le p-1.$

The residue $r_u$ need not be even. To bring it back into the even set $E$ , define

$\displaystyle r'_u := \begin{cases} r_u, & \text{if } r_u \text{ is even},\\ p - r_u, & \text{if } r_u \text{ is odd}. \end{cases}$

Since $p$ is odd, if $r_u$ is odd, then $p-r_u$ is even. Hence every $r'_u$ belongs to $E$ . Moreover, as $u$ runs through $E$ , the values $r'_u$ run through the elements of $E$ exactly once. Thus the map $\displaystyle u \mapsto r'_u$ is a permutation of $E$ .

Now compare $q u$ with $r'_u$ modulo $p$ . If $r_u$ is even, then $r'_u=r_u$ , so $\displaystyle q u \equiv r'_u \pmod{p}.$ If $r_u$ is odd, then $r'_u=p-r_u$ , so $\displaystyle r_u \equiv -r'_u \pmod{p}.$ Therefore, in all cases,

$\displaystyle q\,u \;\equiv\; \begin{cases} r_u, & \text{if } r'_u \text{ is even},\\ -\,r'_u, & \text{if } r_u \text{ is odd}. \end{cases}$

Equivalently

$\displaystyle q u \equiv (-1)^{r_u \bmod 2} r'_u \pmod{p}.$

Multiplying this congruence over all $u\in E$ gives

$\displaystyle q^{M}\,\prod_{u \in E} u \;\equiv\; (-1)^{\sum_{u \in E} (r_u \bmod 2)} \,\prod_{u \in E} r'_u \pmod{p}.$

Since the $r'_u$ are a permutation of $E$ , $\displaystyle \prod_{u\in E} r'_u = \prod_{u\in E} u.$ Since neither product is divisible by $p$ , we cancel $\prod_{u \in E} u$ from both sides to obtain

$\displaystyle q^{M} \;\equiv\; (-1)^{\sum_{u \in E} (r_u \bmod 2)} \pmod{p}.$

By Euler’s Criterion, $\displaystyle \left(\frac{q}{p}\right) \equiv q^{M} \pmod{p}$ when $p \nmid q$ . Thus

$\displaystyle \left(\frac{q}{p}\right) = (-1)^{\sum_{u \in E} (r_u \bmod 2)}$

It remains only to identify this exponent modulo $2$ . For each $u\in E$ , write

$\displaystyle q u = p\left\lfloor \frac{q u}{p} \right\rfloor + r_u.$

Since $u$ is even and $q$ is odd, the product $q u$ is even. Also $p$ is odd. Therefore the parity of $\displaystyle p\left\lfloor \frac{q u}{p} \right\rfloor$ is the same as the parity of $\displaystyle \left\lfloor \frac{q u}{p} \right\rfloor.$

Since the whole left-hand side $q u$ is even, the two terms on the right-hand side must have the same parity. Thus

$\displaystyle r_u \equiv \left\lfloor \frac{q u}{p} \right\rfloor \pmod{2}.$

Summing over $u\in E$ , we obtain

$\displaystyle \sum_{u\in E}(r_u \bmod 2) \equiv \sum_{u\in E}\left\lfloor \frac{q u}{p} \right\rfloor \pmod{2}.$

But the sum on the right is precisely $S_E(q,p)$ . Hence

$\displaystyle \sum_{u\in E}(r_u \bmod 2) \equiv S_E(q,p) \pmod{2}.$

Therefore, $\displaystyle \left(\frac{q}{p}\right)=(-1)^{S_E(q,p)}.$ This proves the lemma. .

From $S_{E}(q,p)$ to $\lambda(q,p)$

Eisenstein’s next insight is that, modulo 2, the sum over even $x$ (namely $S_{E}(q,p)$ ) is congruent to the sum over all $x = 1,2,\dots,\tfrac{p-1}{2}$ , i.e. $\lambda(q,p)$ . We give a streamlined parity argument that shows

$\displaystyle S_{E}(q,p) \;\equiv\; \lambda(q,p) \pmod{2}.$

Recall $\displaystyle S_{E}(q,p) = \sum_{k=1}^{M} \left\lfloor \frac{q\,(2k)}{p} \right\rfloor, \quad x = 2k \in \{2,4,6,\dots,p-1\}.$

Fix a particular even line $x = 2k$ . On that vertical line, all integer lattice points have coordinates $(2k,y)$ with $y = 1,2,\dots,q-1$ . Since $q$ is odd, $q-1$ is even, so there are exactly $q-1$ points on that vertical line between $y=1$ and $y=q-1$ .

The number of points strictly below the line $L: y = \tfrac{q\,x}{p}$ is
$\displaystyle \left\lfloor \tfrac{q\,(2k)}{p} \right\rfloor.$
The number of points strictly above $L$ (but with $1 \le y \le q-1$ ) is
$\displaystyle (q-1) \;-\; \left\lfloor \tfrac{q\,(2k)}{p} \right\rfloor.$

Since $q-1$ is even, it follows that

$\displaystyle \left\lfloor \tfrac{q\,(2k)}{p} \right\rfloor \;\equiv\; (q-1) - \left\lfloor \tfrac{q\,(2k)}{p} \right\rfloor \quad(\bmod 2).$

We can see that

$\displaystyle (q - 1) - \left\lfloor \tfrac{q\,(2k)}{p} \right\rfloor \;=\; \left\lfloor \tfrac{q\,\bigl(p - 2k\bigr)}{p} \right\rfloor,$

where $p - 2k$ is an odd integer in $\{1,3,5,\dots,p-2\}$ . Concretely, each point above the line $L$ on the even column $x=2k$ corresponds to a unique point below $L$ on the odd column $x = p - 2k$ . Hence, for each $k$ ,

$\displaystyle \left\lfloor \tfrac{q\,(2k)}{p} \right\rfloor \;\equiv\; \left\lfloor \tfrac{q\,\bigl(p - 2k\bigr)}{p} \right\rfloor \quad(\bmod 2).$

Comparing to $\lambda(q,p)$

Now break the sum $\displaystyle \lambda(q,p) = \sum_{x=1}^{M} \left\lfloor \tfrac{q\,x}{p} \right\rfloor$ into two parts: one over odd $x$ and one over even $x$ . That is,

$\displaystyle \lambda(q,p) = \sum_{\substack{x=1 \\ x \text{ odd}}}^{M} \left\lfloor \tfrac{q\,x}{p} \right\rfloor \;+\; \sum_{\substack{x=1 \\ x \text{ even}}}^{M} \left\lfloor \tfrac{q\,x}{p} \right\rfloor.$

Observe that the sum over odd $x$ in the range $1 \le x \le M = \tfrac{p-1}{2}$ is exactly

$\displaystyle \sum_{\substack{x = 1 \\ x \text{ odd}}}^{M} \left\lfloor \tfrac{q\,x}{p} \right\rfloor \;=\; \sum_{\substack{x = 1 \\ u=p-x \text{ even}}}^{M} \left\lfloor \tfrac{q\,u}{p} \right\rfloor \quad(\bmod 2).$

which after reindexing matches

$\displaystyle \sum_{\substack{x = \frac{p+1}{2} \\ x \text{ even}}}^{p-1} \left\lfloor \tfrac{q\,x}{p} \right\rfloor \quad(\bmod 2).$

Hence $\displaystyle \lambda(q,p) \equiv \sum_{\substack{x=1 \\ x \text{ even}}}^{p-1} \left\lfloor \tfrac{q\,x}{p} \right\rfloor \;=\; S_{E}(q,p) \quad(\bmod 2).$

Since $\left(\frac{q}{p}\right) = (-1)^{S_{E}(q,p)}$ , we conclude

$\displaystyle \left(\frac{q}{p}\right) = (-1)^{\lambda(q,p)}.$

The Main Geometric Counting Argument

We have now re‐expressed $\displaystyle \left(\frac{q}{p}\right) = (-1)^{\lambda(q,p)}, \left(\frac{p}{q}\right) = (-1)^{\lambda(p,q)},$ where

$\displaystyle \lambda(q,p) = \sum_{x=1}^{(p-1)/2} \left\lfloor \frac{q\,x}{p} \right\rfloor, \quad \lambda(p,q) = \sum_{y=1}^{(q-1)/2} \left\lfloor \frac{p\,y}{q} \right\rfloor.$

We now count all integer points $(x,y)$ in the rectangle

$\displaystyle \mathcal{R} = \Bigl\{ (x,y)\in\mathbb{R}^2 : 0 < x < \tfrac{p}{2}, \; 0 < y < \tfrac{q}{2} \Bigr\},$

with $x,y\in\mathbb{Z}$ . Precisely, we consider

$\displaystyle \bigl\{ (x,y)\in\mathbb{Z}^2 : 1 \le x \le \tfrac{p-1}{2}, \; 1 \le y \le \tfrac{q-1}{2} \bigr\}.$

Since there are $\tfrac{p-1}{2}$ choices for $x$ and $\tfrac{q-1}{2}$ choices for $y$ , the total number of such lattice points is

$\displaystyle N_{\text{total}} = \frac{p-1}{2} \times \frac{q-1}{2}.$

No such lattice point $(x,y)$ lies exactly on the line $\displaystyle L: p\,y = q\,x,$ because if $p\,y = q\,x$ and $1 \le x \le \tfrac{p-1}{2}$ , then $p \mid q\,x$ . Since $p$ and $q$ are distinct primes, $p \nmid q$ , so $p$ must divide $x$ . But $0 < x < p$ forces $x=0$ , which is impossible in our index range. Hence all lattice points in $\mathcal{R}$ are either strictly below $L$ or strictly above $L$ .

The points strictly below $L$ (i.e. satisfying $p\,y < q\,x$ ) are counted by
$\displaystyle \lambda(q,p) = \sum_{x=1}^{(p-1)/2} \#\Bigl\{\,y : 1 \le y < \tfrac{q\,x}{p}\Bigr\} = \sum_{x=1}^{(p-1)/2} \left\lfloor \tfrac{q\,x}{p} \right\rfloor.$
The points strictly above $L$ (i.e. satisfying $p\,y > q\,x$ ) are counted by
$\displaystyle \lambda(p,q) = \sum_{y=1}^{(q-1)/2} \#\Bigl\{\,x : 1 \le x < \tfrac{p\,y}{q}\Bigr\} = \sum_{y=1}^{(q-1)/2} \left\lfloor \tfrac{p\,y}{q} \right\rfloor.$

Since these two sets of points partition all $N_{\text{total}}$ lattice points in $\mathcal{R}$ , we have

$\displaystyle \lambda(q,p) + \lambda(p,q) = N_{\text{total}} = \frac{p-1}{2} \cdot \frac{q-1}{2}.$

Therefore,

$\displaystyle \left(\frac{q}{p}\right)\,\left(\frac{p}{q}\right) = (-1)^{\lambda(q,p)}\,(-1)^{\lambda(p,q)} = (-1)^{\lambda(q,p) + \lambda(p,q)} = (-1)^{\frac{p-1}{2} \,\frac{q-1}{2}}.$

This completes Eisenstein’s geometric proof of the Law of Quadratic Reciprocity.

Concluding Remarks

The beauty of this argument lies in translating an arithmetic statement about Legendre symbols into a purely geometric enumeration problem.
Eisenstein’s parity argument shows that summing over even $x$ -coordinates (the original sum $S_{E}(q,p)$ ) is congruent mod 2 to summing over all $1 \le x \le (p-1)/2$ . This relates the parity of the Eisenstein sum to a sum more geometric.
The final step is a simple but elegant lattice‐point count in a rectangle, divided by a diagonal line of slope $q/p$ . No point in the interior can lie exactly on the diagonal, ensuring that every point is counted either “below” or “above.”

Share this:

Related

Leave a Reply Cancel reply