Counting one rectangle, twice

On a dial of eleven, some numbers are squares and some are not. $1, 3, 4, 5, 9$ are — they are $1^2, 5^2, 2^2, 4^2, 3^2$ — and the other five are not. Asking whether seven is a square modulo eleven is a question with a yes-or-no answer and no obvious structure to it.

Asking the same question the other way round — is eleven a square modulo seven? — looks like a different question about different objects. The two answers are connected, and quadratic reciprocity is the connection.

That figure is the whole theorem. What remains is to say why counting dots on two sides of a line answers two questions about remainders.

The symbol, and the criterion #

Write $\left(\frac{a}{p}\right)$ for $+1$ if $a$ is a non-zero square modulo $p$ and $-1$ if it is not. Euler’s criterion says

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

which follows from Fermat’s little theorem: $a^{p-1} \equiv 1$, so $a^{(p-1)/2}$ squares to one and must be $\pm 1$; and it is $+1$ exactly for the squares, because the squares form the image of a two-to-one map and therefore make up half the residues.

The symbol is multiplicative — $\left(\frac{ab}{p}\right) = \left(\frac{a}{p}\right)\left(\frac{b}{p}\right)$, immediately from the criterion — so knowing it for every prime $q$ determines it for every number. Together with the splitting of a composite modulus, that reduces every question about squares modulo anything to the two-prime case, which is the case reciprocity settles.

Quadratic reciprocity. For distinct odd primes $p$ and $q$,

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

In words: the two questions have the same answer, unless both primes leave remainder three on division by four, in which case they have opposite answers.

Gauss called it the theorema aureum, proved it eight different ways, and it was the result he returned to more often than any other. Over two hundred proofs are now known.

Gauss’s lemma: fold the top half down #

The bridge from the symbol to a count is a lemma about where multiples land.

Take the multiples $q, 2q, \ldots, \tfrac{p-1}{2}q$, reduce them modulo $p$, and fold anything above $p/2$ down by replacing $r$ with $p - r$. Two facts, both visible: the folded values are all different, and they are exactly $1, 2, \ldots, \tfrac{p-1}{2}$ in some order.

Multiplying the original multiples gives $q^{(p-1)/2} \cdot \left(\tfrac{p-1}{2}\right)!$. Multiplying the folded ones gives $\left(\tfrac{p-1}{2}\right)!$ again, with a sign of $-1$ for each fold. Cancelling the factorial,

$$\left(\frac{q}{p}\right) = (-1)^{\text{number of folds}}.$$

So the symbol is a parity, and parities can be counted.

Where the rectangle comes from #

Counting folds is a count of $k$ for which $kq \bmod p$ exceeds $p/2$, and Eisenstein’s contribution — he was twenty when he found it — is that this count has the same parity as a much tidier one:

$$\sum_{k=1}^{(p-1)/2} \left\lfloor \frac{kq}{p} \right\rfloor.$$

And that sum is a count of lattice points. The term $\lfloor kq/p \rfloor$ is the number of whole numbers $y$ with $0 < y < kq/p$ — the lattice points in column $k$ lying below the line $y = qx/p$.

So $\left(\frac{q}{p}\right) = (-1)^{B}$, where $B$ is the number of lattice points strictly below the diagonal of a $\tfrac{p-1}{2}$ by $\tfrac{q-1}{2}$ rectangle.

Now run the same argument with $p$ and $q$ swapped. By symmetry — reflecting the rectangle in its diagonal — the count for $\left(\frac{p}{q}\right)$ is the number of lattice points above the line.

Every point in the rectangle is on one side or the other, because no lattice point lies on the diagonal: a point on $y = qx/p$ would need $py = qx$ with $x < p$ and $y < q$, and since $p$ and $q$ are distinct primes that is impossible. So

$$B + A = \frac{p-1}{2}\cdot\frac{q-1}{2},$$

and multiplying the two symbols gives $(-1)^{B+A}$, which is the theorem.

Why this is a good proof #

The argument is short and its shape is worth naming, because the shape is the reason it explains rather than merely verifies.

The two Legendre symbols look like statements about two different dials. Eisenstein’s count turns each into a statement about one geometric object — the same rectangle, examined from two sides — and the theorem becomes the observation that the two sides of a line account for all of it.

That is counting one collection two ways in its most consequential appearance. There is no computation in it beyond a floor function, no analysis, and no clever substitution; the entire content is that a rectangle has an inside and a diagonal misses every point of it.

It also explains the strange condition. The product of the symbols is $-1$ exactly when $\tfrac{p-1}{2}$ and $\tfrac{q-1}{2}$ are both odd, which is when both primes are $3 \bmod 4$ — and that is just the statement that a rectangle has an odd number of points only when both its sides are odd. A congruence condition that looks arbitrary in the theorem is a parity of a rectangle in the picture.

The clause that carries the most weight is the one easiest to skim: no lattice point lies on the diagonal. Without it the two counts would not add to the total, the parities would not compose, and the theorem would say nothing. It holds because $p$ and $q$ are distinct primes, so $py = qx$ forces $p \mid x$, and $x$ is smaller than $p$. The whole result rests on an emptiness — a line through a grid missing every point of it — which is the same shape of argument as the walk that fills a coprime grid and stalls on a shared factor.

Every figure on this page checks that emptiness explicitly before counting anything, which is the only honest way to draw a proof whose load-bearing step is that something is absent.

Half of everything is a square #

Before the theorem, it is worth being clear about how much structure there is to explain, because the raw facts look like noise.

So on any odd prime dial exactly half the non-zero residues are squares, and the halves are not random: the product of two squares is a square, the product of two non-squares is a square, and the product of a square and a non-square is not. The Legendre symbol is a group homomorphism onto $\{\pm 1\}$, which is why multiplicativity was immediate above.

Beyond that, almost nothing about which residues are squares is predictable from the dial alone. The list for eleven is $1, 3, 4, 5, 9$; for thirteen it is $1, 3, 4, 9, 10, 12$; and no pattern in either list survives to the other. What reciprocity supplies is the only general structure there is, and it does not describe the list — it relates one dial’s answer about a prime to another dial’s answer about a different prime.

That is worth stating plainly because it sets expectations correctly. The theorem does not say which numbers are squares modulo $p$. It says that the answer for $q$ modulo $p$ and the answer for $p$ modulo $q$ are the same question asked twice, and everything computational follows from being able to switch between them.

What the picture cannot show #

The rectangle is drawn for two small primes and the theorem is about all of them. That much is familiar; two other limits are specific to this result.

The picture handles two distinct odd primes, and the theorem has two supplements that no rectangle covers. Whether $-1$ is a square modulo $p$ is decided by $p \bmod 4$, and whether $2$ is a square is decided by $p \bmod 8$. Both are proved by Gauss’s lemma directly — count the folds for $a = -1$ and $a = 2$ — and neither has a rectangle, because $2$ is not an odd prime and $-1$ is not a prime at all. The three statements together are what is actually used, and the drawing carries only the largest of them.

More deeply, the picture explains the mechanism and not the significance. Reciprocity is the first case of a pattern that runs through the whole of algebraic number theory: whether a prime splits in a field is decided by a congruence condition on that prime. Cubic and biquadratic reciprocity extend it; Artin reciprocity, the central theorem of class field theory, is the general statement; and none of that is visible in a rectangle of dots. What the figure shows is exactly why the two-prime case is true and nothing about why anybody would look for a general version.

What it is used for #

Reciprocity is not only beautiful; it is the reason the Legendre symbol can be computed quickly.

Deciding whether $q$ is a square modulo $p$ by Euler’s criterion needs a modular exponentiation. Deciding it by reciprocity needs a sequence of reductions: flip the symbol, reduce the top modulo the bottom, pull out factors of two using the supplement, and repeat. That is Euclid’s algorithm with a sign attached, and it runs in logarithmic time without any exponentiation at all.

The algorithm matters. Solovay–Strassen primality testing compares the Jacobi symbol, computed by reciprocity, against Euler’s criterion, computed by exponentiation, and a mismatch proves compositeness. Deciding whether a quadratic congruence has a solution — needed constantly in factoring algorithms, in elliptic curve arithmetic, and in choosing parameters for cryptographic groups — is a reciprocity computation.

There is a pleasing circularity in that. The theorem says two questions have linked answers; the algorithm exploits the link to answer either one cheaply; and the cheapness is what makes the theorem a tool rather than an ornament.

Working one out by hand #

The algorithm is short enough to run through once, and doing so shows why the theorem is worth having computationally rather than only aesthetically.

Is $219$ a square modulo $383$? Both are odd, $383$ is prime, and $219 = 3 \times 73$. By multiplicativity the question splits, and by reciprocity each piece flips.

$\left(\frac{3}{383}\right)$: both $3$ and $383$ are $3 \bmod 4$, so the symbols are opposite and $\left(\frac{3}{383}\right) = -\left(\frac{383}{3}\right)$. Now $383 \equiv 2 \pmod 3$, and $2$ is not a square modulo $3$, so $\left(\frac{383}{3}\right) = -1$ and the piece is $+1$.

$\left(\frac{73}{383}\right)$: $73 \equiv 1 \pmod 4$, so the symbols agree and this is $\left(\frac{383}{73}\right)$. Reducing, $383 = 5 \times 73 + 18$, so the question becomes $\left(\frac{18}{73}\right) = \left(\frac{2}{73}\right)\left(\frac{9}{73}\right)$. Nine is a square, so that factor is $+1$; and $73 \equiv 1 \pmod 8$, so by the second supplement $\left(\frac{2}{73}\right) = +1$.

So $\left(\frac{219}{383}\right) = +1$ and $219$ is a square modulo $383$ — reached in four lines, without computing a single power, and without finding the square root. Euler’s criterion would have answered the same question with a $191$-fold exponentiation, and for primes of cryptographic size the difference between the two methods is the difference between practical and not.

Notice what the computation never does. It does not produce the number whose square is $219$; deciding whether a square root exists and finding it are separate problems, and the second one is genuinely harder — for a general prime it needs the Tonelli–Shanks algorithm, and modulo a composite it is equivalent to factoring. This is the same split between existence and construction that the pigeonhole argument and Euclid’s proof about primes both run into, and here it has a practical consequence: the ease of the first problem and the difficulty of the second are together the basis of several cryptographic schemes.

Eight proofs, and why #

Gauss found the first proof in 1796, aged nineteen, after a year of work, and published it in the Disquisitiones in 1801. He then published five more and left two in his papers.

The reason for the accumulation is not obsession. Gauss’s first proof is a long induction that convinces without explaining; each later proof came from a different direction — Gauss sums, counting arguments, cyclotomy — and each direction turned out to generalise differently. The proof by Gauss sums is the one that extends to higher reciprocity laws; the counting proof, refined by Eisenstein into the argument above, is the one that can be drawn.

A theorem with two hundred proofs is a theorem sitting at a junction. What the proofs have in common is only the statement; what they differ in is which larger theory they are the first case of, and finding out which of those theories exists was a century of work.

The history before Gauss is worth a line, because the theorem was seen before it was proved. Euler stated it, in a form he could not establish, some thirty years earlier; Legendre published a proof in 1785 that assumed, without noticing, a case of Dirichlet’s theorem on primes in arithmetic progressions — which would not be proved for another fifty years, and whose proof does not use reciprocity, so the argument was repairable rather than circular. Legendre also introduced the symbol and gave the theorem its modern shape.

That pattern — a statement recognised from numerical evidence long before anybody can prove it — is characteristic of this subject and it is the reason the habit of testing a claim matters so much here. Euler had tables. The tables were right, the pattern in them was real, and the distance from seeing it to proving it was three decades and a nineteen-year-old.

Where the ladder goes next #

Quadratic residues decide more than they look. Whether $-1$ is a square modulo $p$ is exactly the condition that decides which primes are sums of two squares, so the first supplement of this theorem and Fermat’s two-square theorem are the same statement in two languages.

The other direction leads out of elementary number theory altogether. The pattern “a congruence condition on $p$ decides how $p$ behaves in a larger structure” is class field theory, and reciprocity is its first and smallest case — reachable, as this essay shows, by drawing fifteen dots and a diagonal.