Quadratic Reciprocity: Gauss's Golden Theorem

Pick two odd primes, say $7$ and $11$. Ask the question: is $7$ a square modulo $11$? That is, does there exist an integer $x$ such that $x^2 \equiv 7 \pmod{11}$? Squaring the residues $1, 2, 3, 4, 5$ modulo $11$ gives $1, 4, 9, 5, 3$ — and the remaining squares ($6$ through $10$) just repeat these in reverse — so the squares modulo $11$ are precisely $\{1, 3, 4, 5, 9\}$. The number $7$ is not in this list. So no, $7$ is not a square modulo $11$.

Now flip the roles: is $11$ a square modulo $7$? Modulo $7$, the number $11$ is $4$, and $4 = 2^2$. So yes, $11$ is a square modulo $7$.

One yes, one no. We have asked a pair of questions that look closely related — they are about the same pair of primes — but no obvious reason connects their answers. Why should there be any pattern at all?

The astonishing fact, first conjectured by Euler and Legendre and first proved by Gauss in 1796 when he was nineteen, is that there is an exact pattern. The two answers are connected by a single short formula, which depends only on the simple question of whether each of $p$ and $q$ leaves remainder $1$ or $3$ when divided by $4$. The result is called the Law of Quadratic Reciprocity, and Gauss was so taken by it that he called it the aureum theorema — the golden theorem. He found eight different proofs of it in his lifetime. This article is about what the law says, why it is mysterious, and what it has grown into in the two centuries since.

The Legendre symbol

The convenient piece of notation is the Legendre symbol, written $\left(\tfrac{a}{p}\right)$ for an odd prime $p$ and an integer $a$ not divisible by $p$. It is defined to be $+1$ if $a$ is a square modulo $p$ (a quadratic residue) and $-1$ if it is not. So with the example above, $\left(\tfrac{7}{11}\right) = -1$ and $\left(\tfrac{11}{7}\right) = +1$.

The Legendre symbol has one critically useful property: it is multiplicative in $a$:

$\left(\frac{ab}{p}\right) = \left(\frac{a}{p}\right)\left(\frac{b}{p}\right).$

This means that if you know which numbers are squares mod $p$ for the primes (and for $-1$), you can compute the Legendre symbol of any non-multiple of $p$ by factoring and multiplying. The whole problem of testing for squareness mod $p$ reduces to a finite list of prime-by-prime cases — provided you have an efficient way to handle each one.

The statement

Gauss’s law gives the relationship between the two Legendre symbols $\left(\tfrac{p}{q}\right)$ and $\left(\tfrac{q}{p}\right)$ for any two 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}}.$

Each of $(p-1)/2$ and $(q-1)/2$ is an integer — even if $p \equiv 1 \pmod 4$, odd if $p \equiv 3 \pmod 4$. So the exponent on the right is even (and the product is $+1$) unless both $p$ and $q$ are congruent to $3$ modulo $4$, in which case the exponent is odd and the product is $-1$.

In plain words: $p$ is a square mod $q$ if and only if $q$ is a square mod $p$ — unless both $p$ and $q$ leave remainder $3$ when divided by $4$, in which case exactly one of the two is a square mod the other. The reciprocity is broken in exactly this small symmetric exceptional case.

For the opening example $p = 7$, $q = 11$: both are $\equiv 3 \pmod 4$, so the rule predicts $\left(\tfrac{7}{11}\right) \cdot \left(\tfrac{11}{7}\right) = -1$. And we computed the two symbols to be $-1$ and $+1$, whose product is indeed $-1$. The rule holds.

A small table

The picture below shows the Legendre symbols $\left(\tfrac{p}{q}\right)$ for the five primes $3, 5, 7, 11, 13$. The cell in row $p$ and column $q$ shows whether $p$ is a square mod $q$. By quadratic reciprocity, the table is almost symmetric — except in pairs where both primes are $\equiv 3 \pmod 4$ (the cells highlighted in red), where the symmetry reverses.

<rect x="190" y="90" width="60" height="34" fill="#fff" stroke="#bbb"/>
<text x="220" y="113" text-anchor="middle" font-family="sans-serif" font-size="14" fill="#c0392b" font-weight="600">−1</text>

<rect x="270" y="90" width="60" height="34" fill="#fde4e4" stroke="#c0392b"/>
<text x="300" y="113" text-anchor="middle" font-family="sans-serif" font-size="14" fill="#c0392b" font-weight="600">−1</text>

<rect x="350" y="90" width="60" height="34" fill="#fde4e4" stroke="#c0392b"/>
<text x="380" y="113" text-anchor="middle" font-family="sans-serif" font-size="14" fill="#2c7a4b" font-weight="600">+1</text>

<rect x="430" y="90" width="60" height="34" fill="#fff" stroke="#bbb"/>
<text x="460" y="113" text-anchor="middle" font-family="sans-serif" font-size="14" fill="#2c7a4b" font-weight="600">+1</text>

<!-- Row p=5 -->
<rect x="110" y="140" width="60" height="34" fill="#fff" stroke="#bbb"/>
<text x="140" y="163" text-anchor="middle" font-family="sans-serif" font-size="14" fill="#c0392b" font-weight="600">−1</text>

<rect x="190" y="140" width="60" height="34" fill="#ddd"/>
<text x="220" y="163" text-anchor="middle" font-family="sans-serif" font-size="14" fill="#666" font-style="italic">—</text>

<rect x="270" y="140" width="60" height="34" fill="#fff" stroke="#bbb"/>
<text x="300" y="163" text-anchor="middle" font-family="sans-serif" font-size="14" fill="#c0392b" font-weight="600">−1</text>

<rect x="350" y="140" width="60" height="34" fill="#fff" stroke="#bbb"/>
<text x="380" y="163" text-anchor="middle" font-family="sans-serif" font-size="14" fill="#2c7a4b" font-weight="600">+1</text>

<rect x="430" y="140" width="60" height="34" fill="#fff" stroke="#bbb"/>
<text x="460" y="163" text-anchor="middle" font-family="sans-serif" font-size="14" fill="#c0392b" font-weight="600">−1</text>

<!-- Row p=7 -->
<rect x="110" y="190" width="60" height="34" fill="#fde4e4" stroke="#c0392b"/>
<text x="140" y="213" text-anchor="middle" font-family="sans-serif" font-size="14" fill="#2c7a4b" font-weight="600">+1</text>

<rect x="190" y="190" width="60" height="34" fill="#fff" stroke="#bbb"/>
<text x="220" y="213" text-anchor="middle" font-family="sans-serif" font-size="14" fill="#c0392b" font-weight="600">−1</text>

<rect x="270" y="190" width="60" height="34" fill="#ddd"/>
<text x="300" y="213" text-anchor="middle" font-family="sans-serif" font-size="14" fill="#666" font-style="italic">—</text>

<rect x="350" y="190" width="60" height="34" fill="#fde4e4" stroke="#c0392b"/>
<text x="380" y="213" text-anchor="middle" font-family="sans-serif" font-size="14" fill="#2c7a4b" font-weight="600">+1</text>

<rect x="430" y="190" width="60" height="34" fill="#fff" stroke="#bbb"/>
<text x="460" y="213" text-anchor="middle" font-family="sans-serif" font-size="14" fill="#c0392b" font-weight="600">−1</text>

<!-- Row p=11 -->
<rect x="110" y="240" width="60" height="34" fill="#fde4e4" stroke="#c0392b"/>
<text x="140" y="263" text-anchor="middle" font-family="sans-serif" font-size="14" fill="#c0392b" font-weight="600">−1</text>

<rect x="190" y="240" width="60" height="34" fill="#fff" stroke="#bbb"/>
<text x="220" y="263" text-anchor="middle" font-family="sans-serif" font-size="14" fill="#2c7a4b" font-weight="600">+1</text>

<rect x="270" y="240" width="60" height="34" fill="#fde4e4" stroke="#c0392b"/>
<text x="300" y="263" text-anchor="middle" font-family="sans-serif" font-size="14" fill="#c0392b" font-weight="600">−1</text>

<rect x="350" y="240" width="60" height="34" fill="#ddd"/>
<text x="380" y="263" text-anchor="middle" font-family="sans-serif" font-size="14" fill="#666" font-style="italic">—</text>

<rect x="430" y="240" width="60" height="34" fill="#fff" stroke="#bbb"/>
<text x="460" y="263" text-anchor="middle" font-family="sans-serif" font-size="14" fill="#c0392b" font-weight="600">−1</text>

<!-- Row p=13 -->
<rect x="110" y="290" width="60" height="34" fill="#fff" stroke="#bbb"/>
<text x="140" y="313" text-anchor="middle" font-family="sans-serif" font-size="14" fill="#2c7a4b" font-weight="600">+1</text>

<rect x="190" y="290" width="60" height="34" fill="#fff" stroke="#bbb"/>
<text x="220" y="313" text-anchor="middle" font-family="sans-serif" font-size="14" fill="#c0392b" font-weight="600">−1</text>

<rect x="270" y="290" width="60" height="34" fill="#fff" stroke="#bbb"/>
<text x="300" y="313" text-anchor="middle" font-family="sans-serif" font-size="14" fill="#c0392b" font-weight="600">−1</text>

<rect x="350" y="290" width="60" height="34" fill="#fff" stroke="#bbb"/>
<text x="380" y="313" text-anchor="middle" font-family="sans-serif" font-size="14" fill="#c0392b" font-weight="600">−1</text>

<rect x="430" y="290" width="60" height="34" fill="#ddd"/>
<text x="460" y="313" text-anchor="middle" font-family="sans-serif" font-size="14" fill="#666" font-style="italic">—</text>

both primes ≡ 3 (mod 4): sign flips otherwise: (p/q) = (q/p)

Look at the cells with white background: across the diagonal, the Legendre symbols match. For example, $\left(\tfrac{3}{5}\right) = -1$ and $\left(\tfrac{5}{3}\right) = -1$; or $\left(\tfrac{5}{11}\right) = +1$ and $\left(\tfrac{11}{5}\right) = +1$. The table is symmetric in these cells. In the red cells — exactly the entries where both primes are $\equiv 3 \pmod 4$ — the sign flips. For example, $\left(\tfrac{3}{7}\right) = -1$ while $\left(\tfrac{7}{3}\right) = +1$. The two values disagree precisely in this exceptional case, and the rule is unfailingly consistent across every pair of primes in the table.

Why this is so surprising

The Legendre symbol $\left(\tfrac{p}{q}\right)$ is an arithmetic question about residues modulo $q$. The Legendre symbol $\left(\tfrac{q}{p}\right)$ is an arithmetic question about residues modulo $p$. These are arithmetic problems in two completely different “worlds” — the integers modulo $p$ and the integers modulo $q$ are different finite arithmetic systems, with no obvious bridge between them.

The astonishing claim of reciprocity is that the answers to these two questions are not independent: they determine each other (up to the one explicit sign factor depending on whether $p$ and $q$ are $\equiv 1$ or $3$ modulo $4$). There is no reason this should be true. The most direct attempts to “see” why it is — by computing the Legendre symbol explicitly using Gauss’s lemma or by counting lattice points in a special rectangle — work, but they do not provide a conceptual reason. The first few proofs Gauss found were essentially clever counting arguments; none of them illuminated the underlying mechanism in a fully satisfying way.

The reason quadratic reciprocity is mysterious is that it is the visible tip of a much larger structure. The modern understanding of why it is true comes from class field theory, which interprets Legendre symbols as describing how the prime $p$ factors in a certain extension field. The clean reciprocity emerges from a deep symmetry between two field extensions — but understanding this requires the apparatus of Galois theory and abstract algebra, none of which existed in Gauss’s day. Gauss could prove the theorem; he could not really explain it.

Gauss’s eight proofs

In his lifetime Gauss returned to quadratic reciprocity repeatedly, eventually publishing eight different proofs that used entirely different techniques: induction, Gauss sums, complex analysis via roots of unity, geometric counting, and others. Each proof revealed a different aspect of the same phenomenon, and Gauss kept producing them because he was never fully satisfied that he understood why the theorem was true, only that it was. Modern proofs continue this tradition — there are now well over two hundred distinct proofs of quadratic reciprocity in the published literature, contributed by Eisenstein, Kronecker, Hilbert, Tate, and many others. No other theorem in mathematics has been re-proved so many times in so many different ways.

What grew from it

Gauss’s golden theorem was the seed of a tradition called reciprocity laws. The next step, cubic reciprocity for primes congruent to $1$ mod $3$, was proved by Eisenstein and Jacobi in the 1840s; biquadratic reciprocity (about fourth powers) was completed soon after. These are statements analogous to Gauss’s but for higher powers, and they have the same general flavour of a deep symmetry connecting different finite arithmetic worlds.

The grand generalisation came with Artin reciprocity, proved by Emil Artin in 1927. It applies to any abelian Galois extension of the rationals (or any number field) and states that the prime factorisation behaviour in the extension is governed by a single homomorphism — the “Artin map” — generalising the Legendre symbol. Artin reciprocity is the centrepiece of class field theory, one of the great twentieth-century achievements of pure mathematics.

The next horizon is the Langlands program, formulated by Robert Langlands starting in 1967 and arguably the largest unifying project in modern pure mathematics. Langlands proposed that there should be a vast generalisation of Artin reciprocity to non-abelian Galois extensions, connecting Galois representations to automorphic forms on adelic groups. The conjectures of the Langlands program are still mostly open, but their solved parts have produced spectacular results — including Andrew Wiles’s proof of Fermat’s Last Theorem in 1995, which essentially established a Langlands-style correspondence for elliptic curves. The thread that runs from a teenage Gauss’s golden theorem all the way to modern automorphic forms is genuinely continuous, and the depth of the connection is one of the most striking features of the mathematical tradition.

A small theorem with the deepest of roots

What started as a quirky empirical observation — that whether $p$ is a square mod $q$ is determined by whether $q$ is a square mod $p$, with one specific exception — turns out to be the first known instance of a vast hidden symmetry in number theory. The pattern is elegant enough that Euler and Legendre conjectured it from numerical experiments. The proof was hard enough that it took Gauss, the leading mathematician of his age, working hard for years. The phenomenon was deep enough that two hundred years of further mathematics have been built on generalising it.

A teenage mathematician in 1796 discovered the entry point to one of the longest research programmes in the history of mathematics. That research programme is still in progress today, and its terminal point — a complete understanding of reciprocity in all its forms — would represent the unification of large parts of number theory and representation theory. Gauss called the theorem golden. He had no idea how right he was.

Frequently asked

Who first proved quadratic reciprocity?

Carl Friedrich Gauss gave the first complete proof in 1796, while he was still a teenager. Adrien-Marie Legendre had stated the law in 1785 but his proof had a serious gap (he assumed without justification that certain primes existed in particular arithmetic progressions — a fact only later established by Dirichlet's theorem on primes). Euler had also experimentally observed special cases of the law. Gauss called the theorem 'aureum theorema' (the golden theorem) and was so fond of it that he eventually published eight different proofs, each using fundamentally different techniques. He published the first proof when he was nineteen.

What is the Legendre symbol?

The Legendre symbol (a/p), for an odd prime p and integer a not divisible by p, is +1 if a is a quadratic residue mod p (i.e., a ≡ x² mod p for some x) and −1 if a is a non-residue. It is a compact notation for one bit of information: 'can you solve x² ≡ a mod p?' This symbol turns out to be completely multiplicative in its top argument — (ab/p) = (a/p)(b/p) — which is what makes the theory of quadratic residues feasible at all.

Why is the theorem called 'reciprocity'?

Because it expresses a duality between the roles of p and q: whether p is a square mod q is determined, up to one explicit sign, by whether q is a square mod p. There is no obvious reason why these two facts — one about arithmetic modulo p, the other about arithmetic modulo q — should be related at all. The astonishing assertion of the theorem is that they are, with a relationship as simple and clean as could be hoped for. The word 'reciprocity' captures exactly this back-and-forth symmetry between the two primes.

How is quadratic reciprocity used today?

It is the foundation of efficient algorithms for primality testing (the Solovay–Strassen test) and for computing square roots modulo a prime. More importantly, it is the prototype for a vast generalisation called Artin reciprocity (1927), which extends the symmetry to higher-degree extensions of the rationals and is the centrepiece of class field theory. The Langlands program — one of the largest unifying projects in modern mathematics — is, in part, an attempt to generalise reciprocity further, to non-abelian extensions and to automorphic forms. Quadratic reciprocity is small, beautiful, and the entry point for some of the deepest mathematics there is.

Continue reading

Person

Carl Friedrich Gauss

Often called the 'Prince of Mathematicians', Gauss made profound contributions across nearly every mathematical field, from number theory to differential geometry.

Read →Blog

The Riemann Zeta Function: A Sum That Knows Where the Primes Are

Add up the reciprocals of the powers of every whole number and you get a function that secretly encodes the location of every prime — and the deepest unsolved problem in mathematics.

Read →Blog

The Distribution of Primes: Order in the Random

Primes appear seemingly without pattern. Yet they thin out at a precise rate captured by one of the most beautiful theorems in mathematics — and the most famous unsolved problem hides inside it.

Read →