🔢 mathematics

Zolotarev's Magical Proof of Quadratic Reciprocity

This paper presents a creative reimagining of Zolotarev's classical proof of the Law of Quadratic Reciprocity.

Original authors: Matthew Baker

Published 2026-03-03

📖 6 min read🧠 Deep dive

Original authors: Matthew Baker

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are at a magic show. The magician, a brilliant mathematician named Egor Zolotarev (who tragically died young), is about to perform a trick that connects two seemingly unrelated worlds: shuffling cards and number theory.

This paper, written by Matthew Baker, is a guide to that trick. It uses a deck of cards to prove one of the most famous and beautiful laws in mathematics: The Law of Quadratic Reciprocity.

Here is the story of the trick, broken down into the three acts mentioned in the introduction.

Act 1: The Pledge (The Setup)

The Ordinary Object: A deck of $m \times n$ cards, numbered from 0 to $mn-1$.

The magician lays these cards out on a table in a rectangle. He does this in two different ways:

Row Deal: He fills the first row, then the second, then the third.
Column Deal: He fills the first column, then the second, then the third.

The Trick:
If you look at the card in the top-left corner, it's the same in both layouts. But if you look at the card in the middle, it has moved! The "Row Deal" card is now in a different spot in the "Column Deal."

The magician asks: "How many swaps does it take to turn the Row Deal into the Column Deal?"

In math, this is called the "sign" of the permutation. If you need an even number of swaps, the sign is positive (+1). If you need an odd number, the sign is negative (-1).

The Reveal:
The paper proves a simple formula for this sign. It depends entirely on whether $m$ and $n$ are odd or even.

If both $m$ and $n$ are odd, the sign is positive unless both are "3 more than a multiple of 4" (like 3, 7, 11). In that specific case, the sign is negative.

This is just a combinatorial puzzle about shuffling cards. But the magician hints: This pattern looks suspiciously like a famous rule about prime numbers.

Act 2: The Turn (The Twist)

The Extraordinary Move:
Now, the magician introduces a third way to deal the cards: The Diagonal Deal.
Imagine dealing cards diagonally, wrapping around the edges of the table like a video game character walking off the screen and reappearing on the other side.

He creates a new permutation (a new shuffling pattern) by comparing the Row Deal to this Diagonal Deal.

The Connection:
Here is the magic. The sign of this diagonal shuffle isn't just a random number. It turns out to be exactly the same as the sign of a very specific mathematical operation: Multiplying numbers by $n$ inside a clock system of size $m$ .

Imagine a clock with $m$ hours.
If you multiply every hour by $n$ , the numbers jump around.
The "sign" of that jump is the same as the sign of our card shuffle.

The paper then uses a clever trick of symmetry. It compares the Row Deal, the Column Deal, and the Diagonal Deal. By multiplying the signs of these shuffles together, the magician derives a new equation:

$\text{Sign}(m \text{ on } n) \times \text{Sign}(n \text{ on } m) = \text{The Card Shuffle Sign}$

This equation looks exactly like the Law of Quadratic Reciprocity, but it's still just about card shuffles and clocks. We haven't talked about "squares" yet.

Act 3: The Prestige (The Grand Finale)

The Disappearance and Return:
The audience is hooked, but they are confused. "Okay," they say, "you proved a rule about card shuffles. But what does that have to do with whether a number is a perfect square modulo a prime?"

This is where the "Prestige" happens. The magician reveals the secret link between the card shuffles and the squares.

Zolotarev's Lemma:
The paper proves a stunning fact:

The sign of the card shuffle (multiplying by $a$ on a clock of size $p$ ) is exactly the same as the Legendre Symbol $\left(\frac{a}{p}\right)$ .

What is the Legendre Symbol? It's a simple yes/no question:

Is $a$ a perfect square in the world of clock arithmetic modulo $p$ ?
If Yes, the answer is $+1$ .
If No, the answer is $-1$.

The Final Reveal:
Because the card shuffle sign is the Legendre symbol, the equation the magician derived in Act 2 (about card shuffles) automatically becomes the Law of Quadratic Reciprocity.

The Law of Quadratic Reciprocity states:

If you have two different odd prime numbers, $p$ and $q$ , then whether $p$ is a square modulo $q$ and whether $q$ is a square modulo $p$ are linked. They are either both "yes" or both "no," unless both primes are "3 more than a multiple of 4," in which case one is "yes" and the other is "no."

The paper shows that this deep, mysterious law of numbers is actually just a consequence of how cards shuffle when you deal them in rows, columns, and diagonals.

The Bonus: The "Supplements"

The paper ends with a bonus trick. It uses a similar card-dealing method (a "Zigzag" deal) to prove the rules for two special cases:

The number 2: When is 2 a perfect square modulo a prime?
The number -1: When is -1 a perfect square modulo a prime?

By shuffling a deck of cards in a zigzag pattern, the magician derives the exact formulas for these questions, proving that even these specific rules are just variations of the same card-shuffling logic.

Summary

In simple terms, this paper says:
Mathematics is full of hidden connections.
A complex rule about prime numbers and perfect squares (Quadratic Reciprocity) can be understood by simply imagining how a deck of cards moves when you deal them in different patterns. Zolotarev's "magical" proof strips away the heavy algebra and replaces it with the intuitive logic of a card trick.

The "magic" isn't that the math is fake; it's that the math is so deep that it can be explained by something as simple as dealing cards.

Based on the provided text, here is a detailed technical summary of Matthew Baker's paper, "Zolotarev's Magical Proof of Quadratic Reciprocity."

1. Problem Statement

The paper addresses the Law of Quadratic Reciprocity, a fundamental theorem in number theory that describes the relationship between the solvability of quadratic congruences modulo two distinct odd primes $p$ and $q$ . Specifically, it seeks to prove the identity:
$\left(\frac{p}{q}\right) \left(\frac{q}{p}\right) = (-1)^{\frac{(p-1)(q-1)}{4}}$
where $\left(\frac{a}{p}\right)$ is the Legendre symbol. The paper aims to provide a proof that is combinatorial and visual, avoiding the heavy algebraic machinery often associated with standard proofs, by reimagining a classic 1872 proof by Egor Ivanovich Zolotarev through the metaphor of "dealing cards."

2. Methodology

The author employs a combinatorial approach using permutations of finite sets, visualized as card-dealing operations on an $m \times n$ grid. The methodology is structured in three acts (The Pledge, The Turn, The Prestige):

The Pledge (Combinatorial Setup):
- Consider a set of $mn$ cards labeled $0, \dots, mn-1$ .
- Two arrangements are defined: Row deal (R) and Column deal (C).
- The transition from (R) to (C) defines a permutation $\gamma$ .
- The sign of this permutation, $\text{sign}(\gamma)$ , is calculated by counting inversions. An inversion occurs when a card at position $(i, j)$ in (R) moves to a position $(i', j')$ in (C) such that the relative order is reversed.
- Result: The number of inversions is $\binom{m}{2}\binom{n}{2}$ , leading to $\text{sign}(\gamma) = (-1)^{\binom{m}{2}\binom{n}{2}}$ . For odd $m, n$ , this simplifies to $(-1)^{\frac{(m-1)(n-1)}{4}}$ .
The Turn (Diagonal Dealing and Permutation Signs):
- A third arrangement, Diagonal deal (D), is introduced (dealing diagonally with wrapping, effectively on a torus).
- The transition from (R) to (D) defines a permutation $\alpha$ , and from (D) to (C) defines $\beta$ .
- Key Insight: The sign of $\alpha$ corresponds to the sign of the permutation of $\mathbb{Z}/m\mathbb{Z}$ induced by multiplication by $n$ . This is denoted as the "Zolotarev symbol" $\left[\frac{n}{m}\right]$ .
- By symmetry, $\text{sign}(\beta) = \left[\frac{m}{n}\right]$ .
- Since $\gamma = \beta \circ \alpha$ , the signs multiply: $\left[\frac{m}{n}\right] \left[\frac{n}{m}\right] = \text{sign}(\gamma) = (-1)^{\frac{(m-1)(n-1)}{4}}$ .
The Prestige (Connecting to Number Theory):
- Zolotarev's Lemma: The paper proves that for an odd prime $p$ and integer $a$ not divisible by $p$ , the Zolotarev symbol $\left[\frac{a}{p}\right]$ (the sign of the permutation of $\mathbb{Z}/p\mathbb{Z}$ induced by multiplication by $a$ ) is equal to the Legendre symbol $\left(\frac{a}{p}\right)$ .
- Proof of Lemma: The multiplicative group $(\mathbb{Z}/p\mathbb{Z})^\times$ is cyclic. The map $a \mapsto \left[\frac{a}{p}\right]$ is a surjective homomorphism to $\{\pm 1\}$ . Its kernel is a subgroup of index 2, which must be the group of quadratic residues. Thus, the symbols coincide.
- Final Derivation: Substituting the Legendre symbol for the Zolotarev symbol in the equation derived in "The Turn" yields the Law of Quadratic Reciprocity.

3. Key Contributions

Reimagining Zolotarev's Proof: The paper provides a modern, accessible exposition of Zolotarev's 1872 proof, which is historically significant but less known than Gauss's proofs.
Visual/Combinatorial Intuition: By using the "card dealing" metaphor, the author translates abstract algebraic concepts (permutation signs, group homomorphisms) into concrete combinatorial operations (inversions, row/column/diagonal arrangements).
Generalization: The paper notes that this method generalizes to the Jacobi symbol for relatively prime odd integers, not just primes, facilitating the computation of Legendre symbols.
Supplements: The "Director's Cut Bonus Footage" extends the methodology to prove the supplementary laws of quadratic reciprocity:
- $\left(\frac{2}{p}\right) = (-1)^{\frac{p^2-1}{8}}$
- $\left(\frac{-1}{p}\right) = (-1)^{\frac{p-1}{2}}$
  These are derived using a $2 \times m$ grid and a "Zigzag" dealing pattern.

4. Results

Formula (1): The sign of the permutation converting a row deal to a column deal is $(-1)^{\binom{m}{2}\binom{n}{2}}$ .
Formula (3): The sign of the permutation converting a row deal to a diagonal deal is equal to the Zolotarev symbol $\left[\frac{n}{m}\right]$ .
Formula (4): The product of the Zolotarev symbols satisfies $\left[\frac{m}{n}\right] \left[\frac{n}{m}\right] = (-1)^{\frac{(m-1)(n-1)}{4}}$ .
Main Theorem: Combining the above with Zolotarev's Lemma yields the Law of Quadratic Reciprocity for distinct odd primes $p$ and $q$ .

5. Significance

Educational Value: The paper serves as an excellent pedagogical tool, demystifying a deep number-theoretic result through elementary combinatorics and visual reasoning. It bridges the gap between discrete mathematics (permutations) and algebraic number theory.
Historical Context: It highlights the work of Egor Ivanovich Zolotarev, a Russian mathematician whose career was cut short by a train accident at age 31, ensuring his elegant proof receives wider recognition.
Conceptual Clarity: The proof demonstrates that the Law of Quadratic Reciprocity is fundamentally a statement about the parity of permutations induced by multiplication in modular arithmetic, rather than just a property of quadratic residues. This perspective unifies the "supplements" and the main law under a single combinatorial framework.