The Hidden Connection That Changed Number Theory

There are three kinds of prime numbers. The first is a solitary outlier: 2, the only even prime. After that, half the primes leave a remainder of 1 when divided by 4. The other half leave a remainder of 3. (5 and 13 fall in the first camp, 7 and 11 in the second.) There is no obvious reason that remainder-1 primes and remainder-3 primes should behave in fundamentally different ways. But they do.

One key difference stems from a property called quadratic reciprocity, first proved by Carl Gauss, arguably the most influential mathematician of the 19th century. “It’s a fairly simple statement that has applications everywhere, in all sorts of math, not just number theory,” said James Rickards, a mathematician at the University of Colorado, Boulder. “But it’s also non-obvious enough to be really interesting.”

Number theory is a branch of mathematics that deals with whole numbers (as opposed to, say, shapes or continuous quantities). The prime numbers — those divisible only by 1 and themselves — are at its core, much as DNA is core to biology. Quadratic reciprocity has changed mathematicians’ conception of how much it’s possible to prove about them. If you think of prime numbers as a mountain range, reciprocity is like a narrow path that lets mathematicians climb to previously unreachable peaks and, from those peaks, see truths that had been hidden.

Although it’s an old theorem, it continues to have new applications. This summer, Rickards and his colleague Katherine Stange, together with two students, disproved a widely accepted conjecture about how small circles can be packed inside a bigger one. The result shocked mathematicians. Peter Sarnak, a number theorist at the Institute for Advanced Study and Princeton University, spoke with Stange at a conference soon after her team posted their paper. “She told me she has a counterexample,” Sarnak recalled. “I immediately asked her, ‘Are you using reciprocity somewhere?’ And that was indeed what she was using.’”

Patterns in Pairs of Primes

To understand reciprocity, you first need to understand modular arithmetic. Modular operations rely on calculating remainders when you’re dividing by a number called the modulus. For example, 9 modulo 7 is 2, because if you divide 9 by 7, you are left with a remainder of 2. In the modulo 7 number system, there are 7 numbers: {0, 1, 2, 3, 4, 5, 6}. You can add, subtract, multiply and divide these numbers.

Just as with the integers, these number systems can have perfect squares —numbers that are the product of another number times itself. For example, 0, 1, 2 and 4 are the perfect squares modulo 7 (0 × 0 = 0, 1 × 1 = 1, 2 × 2 = 4, and 3 × 3 = 2 mod 7). Every ordinary square will be equal to either 0, 1, 2 or 4 modulo 7. (For example, 6 × 6 = 36 = 1 mod 7.)  Because modular number systems are finite, perfect squares are more common.

Quadratic reciprocity stems from a relatively straightforward question. Given two primes p and q, if you know that p is a perfect square modulo q, can you say whether or not q is a perfect square modulo p?

It turns out that as long as either p or q leaves a remainder of 1 when divided by 4, if p is a perfect square modulo q, then q is also a perfect square modulo p. The two primes are said to reciprocate.

On the other hand, if both of them leave a remainder of 3 (like, say, 7 and 11) then they don’t reciprocate: If p is a square modulo q, that means that q will not be a square modulo p. In this example, 11 is a square modulo 7, since 11 = 4 mod 7 and we already know that 4 is one of the perfect squares modulo 7. It follows that 7 is not a square modulo 11. If you take the list of ordinary squares (4, 9, 16, 25, 36, 49, 64, …) and look at their remainders modulo 11, then 7 will never appear.

This, to use a technical term, is really weird!

The Power of Generalization

Like many mathematical ideas, reciprocity has been influential because it can be generalized.

Soon after Gauss published the first proof of quadratic reciprocity in 1801, mathematicians tried to extend the idea beyond squares. “Why not third powers or fourth powers? They imagined maybe there’s a cubic reciprocity law or quartic reciprocity law,” said Keith Conrad, a number theorist at the University of Connecticut.

But they got stuck, Conrad said, “because there’s no easy pattern.” This changed once Gauss brought reciprocity into the realm of complex numbers, which add the square root of minus 1, represented by i, to ordinary numbers. He introduced the idea that number theorists could analyze not only ordinary integers but other integer-like mathematical systems, like so-called Gaussian integers, which are complex numbers whose real and imaginary parts are both integers.

With Gaussian integers, the whole notion of what counts as prime changed. For example, 5 is no longer prime, because 5 = (2 + i) × (2 − i). “You have to start over like you’re in elementary school again,” Conrad said. In 1832, Gauss proved a quartic reciprocity law for the complex integers that bear his name.

Suddenly, mathematicians learned to apply tools like modular arithmetic and factorization to these new number systems. Quadratic reciprocity was the inspiration, according to Conrad.

Patterns that had been elusive without complex numbers now started to emerge. By the mid-1840s Gotthold Eisenstein and Carl Jacobi had proved the first cubic reciprocity laws.

Then, in the 1920s, Emil Artin, one of the founders of modern algebra, discovered what Conrad calls the “ultimate reciprocity law.” All the other reciprocity laws could be seen as special cases of Artin’s reciprocity law.

A century later, mathematicians are still devising new proofs of Gauss’s first quadratic reciprocity law and generalizing it to novel mathematical contexts. Having many distinct proofs can be useful. “If you want to extend the result to a new setting, maybe one of the arguments will easily carry over, while the other ones won’t,” Conrad said.

Why Reciprocity Is So Useful

Quadratic reciprocity is used in areas of research as diverse as graph theory, algebraic topology and cryptography. In the latter, an influential public key encryption algorithm developed in 1982 by Shafi Goldwasser and Silvio Micali hinges on multiplying two large primes p and q together and outputting the result, N, along with a number, x, which is not a square modulo N. The algorithm uses N and x to encrypt digital messages into strings of larger numbers. The only way to decrypt this string is to decide whether or not each number in the encrypted string is a square modulo N — virtually impossible without knowing the values of the primes p and q.

And of course, quadratic reciprocity crops up repeatedly within number theory. For instance, it can be used to prove that any prime number equal to 1 modulo 4 can be written as the sum of two squares (for example, 13 equals 1 modulo 4, and 13 = 4 + 9 = 2² + 3²). By contrast, primes equal to 3 modulo 4 can never be written as the sum of two squares.

Sarnak noted that reciprocity might be used to solve open questions, like figuring out which numbers can be written as the sum of three cubes. It’s known that numbers that are equal to 4 or 5 modulo 9 are not equal to the sum of three cubes, but others remain a mystery. (In 2019, Andrew Booker generated headlines when he discovered that (8,866,128,975,287,528)³ + (−8,778,405,442,862,239)³ + (−2,736,111,468,807,040)³ = 33.)

For all its many applications, and many different proofs, there is something about reciprocity that remains a mystery, Stange said.

“What often happens with a mathematical proof is you can follow every step; you can believe that it’s true,” she said. “And you can still come out the other end feeling like, ‘But why?’”

Understanding, at a visceral level, what makes 7 and 11 different from 5 and 13 might be forever beyond reach. “We can only juggle so many levels of abstraction,” she said. “It shows up all over the place in number theory … and yet it’s just a step beyond what feels like you could really just know.”