The Law of Quadratic Reciprocity

Carl Friedrich Gauss — arguably the greatest mathematician who ever lived — called this next result his theorema aureum, the "golden theorem". He found his first proof of it at nineteen, in 1796, and it mattered so much to him that he kept coming back to it for the rest of his career, eventually publishing eight different proofs using eight completely different methods. No other single theorem earned that much of his attention.

What makes it worth eight proofs? It links two questions that look like they should have nothing to do with each other: "is p a square modulo q?" and "is q a square modulo p?" Those are two entirely separate computations, about two different moduli, with no obvious reason to be connected. And yet — for any two odd primes p and q, the two answers are almost always exactly the same, tied together by one crisp rule about how p and q sit modulo 4. Reciprocity — literally, a two-way relationship — is exactly the right name.

Here's a taste of just how surprising the connection is, before we state the rule precisely. Is 3 a square mod 13? Checking the squares mod 13 — 1, 4, 9, 3, 12, 10 for 1 through 6 — yes, since 4^2 \equiv 3. Now flip the question completely: is 13 a square mod 3? Reducing first, 13 \equiv 1 \pmod 3, and 1 = 1^2 is trivially a square — so yes again. Two different-looking searches, over two different moduli, using no shared machinery — and they agree. That is not a coincidence; it is the golden theorem quietly at work, and by the end of this page you'll be able to predict that kind of agreement (or, sometimes, disagreement) without checking either list of squares at all.

The law

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}}.

The exponent is even unless both primes are \equiv 3 \pmod 4. So:

Notice this rule needs both moduli checked mod 4 — it's a statement about the pair (p, q) together, not about either prime alone.

The supplements

The law as stated only compares two odd primes to each other. Two companion rules (the "supplements") finish the job for the special tops -1 and 2, which aren't odd primes themselves and so fall outside the main statement — these are exactly the facts Euler's criterion proves directly:

\left(\frac{-1}{p}\right) = (-1)^{\frac{p-1}{2}}, \qquad \left(\frac{2}{p}\right) = (-1)^{\frac{p^2-1}{8}}.

The first says -1 is a square mod p exactly when p \equiv 1 \pmod 4. The second says 2 is a square modulo p exactly when p \equiv \pm 1 \pmod 8. Together with the main law, these three facts let you evaluate any Legendre symbol \left(\tfrac{a}{p}\right) by factoring a into primes and handling each factor in turn — the multiplicativity of the symbol (\left(\tfrac{ab}{p}\right) = \left(\tfrac{a}{p}\right)\left(\tfrac{b}{p}\right)) does the combining.

Worked example: flipping a hard symbol into an easy one

Is 3 a square modulo 13? Squaring every residue from 1 to 12 would answer it eventually, but reciprocity answers it in two lines. Since 13 \equiv 1 \pmod 4, the "at least one is \equiv 1 \pmod 4" case applies, so the symbol flips with no sign change:

\left(\frac{3}{13}\right) = \left(\frac{13}{3}\right).

Now reduce the top modulo the (new, much smaller) bottom: 13 \equiv 1 \pmod 3, so \left(\tfrac{13}{3}\right) = \left(\tfrac{1}{3}\right) = +1 (anything congruent to a perfect square, and 1 always is one, gives +1). Chaining it together:

\left(\frac{3}{13}\right) = \left(\frac{13}{3}\right) = \left(\frac{1}{3}\right) = +1.

Yes — and a quick check confirms it directly: 4^2 = 16 \equiv 3 \pmod{13}. No squaring of all twelve residues was needed; flip-and-reduce, exactly like a Euclidean algorithm running on top and bottom of the symbol instead of on two numbers, cracked it in two steps.

Now try one where the sign genuinely flips. Is 7 a square modulo 19? Check the moduli first: 7 \equiv 3 \pmod 4 and 19 \equiv 3 \pmod 4 — both are \equiv 3 \pmod 4, so this time the symbols are opposite:

\left(\frac{7}{19}\right) = -\left(\frac{19}{7}\right) = -\left(\frac{5}{7}\right)

since 19 \equiv 5 \pmod 7. A short check of squares mod 7 (1, 4, 2, 2, 4, 1 for 1 through 6) shows the residues mod 7 are \{1, 2, 4\}, so 5 is a non-residue and \left(\tfrac{5}{7}\right) = -1. Putting the minus sign from the flip back in: \left(\tfrac{7}{19}\right) = -(-1) = +1. Miss that both primes are \equiv 3 \pmod 4 and you'd forget the extra sign flip and land on the wrong answer.

One more, to see the flip-and-reduce process chain several times in a row. Is 29 a square modulo 43? Both are odd primes, and 29 \equiv 1 \pmod 4, so the flip carries no sign change:

\left(\frac{29}{43}\right) = \left(\frac{43}{29}\right) = \left(\frac{14}{29}\right)

using 43 \equiv 14 \pmod{29}. Now split 14 = 2 \cdot 7 using multiplicativity: \left(\tfrac{14}{29}\right) = \left(\tfrac{2}{29}\right)\left(\tfrac{7}{29}\right). The first factor comes from the second supplement: 29 \equiv 5 \pmod 8, which is not \pm 1 \pmod 8, so \left(\tfrac{2}{29}\right) = -1. For the second factor, flip again — both 7 and 29 are checked mod 4: 7 \equiv 3, 29 \equiv 1, so at least one is \equiv 1 \pmod 4 and the sign stays positive:

\left(\frac{7}{29}\right) = \left(\frac{29}{7}\right) = \left(\frac{1}{7}\right) = +1

since 29 \equiv 1 \pmod 7. Multiplying the pieces back together: \left(\tfrac{14}{29}\right) = (-1)(+1) = -1, so \left(\tfrac{29}{43}\right) = -1 — 29 is not a square modulo 43. Three small flips, each one shrinking the numbers involved, replaced what would otherwise be a search through twenty-one squares mod 43.

The single most common slip with reciprocity is checking only one of the two primes modulo 4 and assuming that settles it. It doesn't — the sign-flip rule is a statement about the pair. Concretely:

A good habit: before flipping a symbol, write down both residues mod 4 explicitly (not just mod 2, i.e. not just "odd") and only then decide the sign. It takes five extra seconds and prevents the single most frequent reciprocity mistake.

Mathematicians usually move on once a theorem is proved — a proof settles the truth, and a second proof of the same fact doesn't make it any truer. So why did Gauss, over a working life packed with first-rate discoveries in almost every branch of mathematics, keep returning to reciprocity again and again, eventually racking up eight independent proofs?

Partly it was dissatisfaction: his first proof (age nineteen) was a brute, awkward induction that worked but explained nothing about why the result was true. Partly it was ambition: each new proof used a different toolkit — Gauss sums, counting lattice points, properties of cyclotomic numbers — and each new toolkit turned out to generalize to deeper questions about higher-power residues (cubes, fourth powers, and beyond) that ordinary quadratic reciprocity couldn't touch. Chasing better proofs of one theorem is how Gauss built entire new branches of number theory as a side effect. When history's most prolific mathematician treats a single result as worth revisiting for decades, that alone is a strong hint you've found something unusually deep — and indeed, reciprocity laws for cubes, fourth powers and beyond (conjectured by Gauss and Eisenstein, eventually explained in full generality by class field theory) are still an active engine of modern number theory.

There's a lighter reading too: reciprocity was, in a sense, Gauss's favourite puzzle to keep solving a new way — the mathematical equivalent of a musician returning to the same melody across a career and finding a fresh arrangement each time. When someone with Gauss's range of interests (he also gave us the normal distribution, the method of least squares, and foundational work in magnetism and geodesy) treats one theorem as worth an eighth attempt, that persistence is itself a signal: this is one of the results everything else quietly depends on.

Turning a search into an algorithm

Put the main law and the two supplements together and something bigger than a party trick emerges: any Legendre symbol \left(\tfrac{a}{p}\right) can be evaluated in a number of steps proportional to the number of digits of a and p — never by testing squares one at a time. Reduce a mod p, peel off factors of 2 using the second supplement, flip the remaining odd part using the main law, reduce again, and repeat — exactly the same shrinking pattern that makes the Euclidean algorithm fast for greatest common divisors. That efficiency is precisely why reciprocity, not brute-force squaring, is the tool real number-theory software reaches for. Extending the symbol so the bottom can be an odd composite number gives the Jacobi symbol, which makes this flip-and-reduce process work as a clean algorithm even when you don't know the factorization of the bottom.