The symbol is the sign of a shuffle

Take the residues modulo eleven, multiply every one of them by three, and write down where each went. Nothing has been created or destroyed: the eleven residues have been rearranged among themselves.

A rearrangement of a finite set has a sign, $+1$ or $-1$, and it is the one bit of information that survives every way of writing the rearrangement down. A rearrangement of the residues modulo $p$ has a Legendre symbol attached to the number doing the rearranging. These are two entirely unrelated-looking constructions on the same object.

They are the same. That is Zolotarev’s theorem, published in 1872, and it is the shortest route from a question about squares to a proof of quadratic reciprocity.

Multiplication really is a rearrangement #

Fix an odd prime $p$ and a residue $a$ not divisible by $p$. The map $x \mapsto ax \bmod p$ sends the set $\{0, 1, \ldots, p-1\}$ to itself, and it is one-to-one, because $ax \equiv ay$ implies $a(x-y) \equiv 0$, and $p$ being prime and not dividing $a$ forces $x \equiv y$.

So $\pi_a$ is a permutation of $p$ things. It fixes $0$ and shuffles the other $p-1$.

Its cycle structure is not arbitrary. Following $1 \mapsto a \mapsto a^2 \mapsto \cdots$ returns to $1$ after exactly $d$ steps, where $d$ is the multiplicative order of $a$ — and starting anywhere else gives a cycle of the same length $d$, because the orbit of $x$ is $x$ times the orbit of $1$. So the moved residues split into $(p-1)/d$ cycles of length $d$, all the same size.

That regularity is the whole of the computation. A cycle of length $d$ is $d-1$ transpositions, so

$$\operatorname{sign}(\pi_a) = (-1)^{(p-1) - (p-1)/d} = (-1)^{(p-1)(1 - 1/d)}.$$

Where the sign comes out #

Write $p - 1 = d \cdot m$, so there are $m$ cycles of length $d$ and the exponent above is $p - 1 - m$. Since $p-1$ is even, the sign is $-1$ exactly when $m$ is odd — that is, exactly when the number of cycles is odd.

Now bring in the group structure. The non-zero residues form a cyclic group of order $p-1$; fix a generator $g$ and write $a = g^k$. The order of $a$ is $d = (p-1)/\gcd(k, p-1)$, so the number of cycles is $m = \gcd(k, p-1)$.

$p-1$ is even, so $\gcd(k, p-1)$ is odd exactly when $k$ is odd. And $a = g^k$ is a square exactly when $k$ is even. So:

• $a$ a square $\iff$ $k$ even $\iff$ $m$ even $\iff$ $\operatorname{sign}(\pi_a) = +1$;
• $a$ a non-square $\iff$ $k$ odd $\iff$ $m$ odd $\iff$ $\operatorname{sign}(\pi_a) = -1$.

Which is to say $\operatorname{sign}(\pi_a) = \left(\frac{a}{p}\right)$, and the proof is four lines long once the cyclic structure is available.

The extreme cases make it vivid #

If $a$ is a generator, there is exactly one cycle, of length $p-1$. One cycle of even length is an odd permutation, so a generator is never a square — which is obvious for a different reason, since a square has order dividing $(p-1)/2$.

If $a = 1$, the permutation is the identity: $p-1$ cycles of length one, and $p-1$ is even, so the sign is $+1$. And $1$ is a square. Consistent, and the smallest case.

If $a = -1$, the permutation pairs each $x$ with $p - x$: that is $(p-1)/2$ transpositions, so the sign is $(-1)^{(p-1)/2}$ — which is the first supplement, arriving here as a count of two-cycles rather than as an exponent. Two proofs of the same statement that share no step.

The cycle count, worked through at eleven #

It is worth doing one modulus completely, because the pattern in the numbers is the theorem in disguise.

Modulo eleven the non-zero residues form a cyclic group of order ten, and $2$ is a generator: its powers run $2, 4, 8, 5, 10, 9, 7, 3, 6, 1$, which is all ten of them. So every residue is $2^k$ for exactly one $k$ between $1$ and $10$, and the squares are the even powers — $4, 5, 9, 3, 1$, which is five residues, as the counting argument requires.

Now take the multipliers one at a time. Multiplication by $2$ has order ten, so one cycle of length ten: nine transpositions, odd, sign $-1$, and $2$ is indeed a non-square. Multiplication by $3 = 2^8$ has order $10/\gcd(8,10) = 5$, so two cycles of length five: each is four transpositions, eight in all, even, sign $+1$ — and $3 = 2^8$ is an even power, so a square. Multiplication by $10 = -1$ has order two: five cycles of length two, five transpositions, odd, sign $-1$, and $-1$ is not a square modulo eleven because $11 \equiv 3 \pmod 4$.

Every line of that is a count of cycles and every line lands on the right answer. The gear connecting them is the identity $m = \gcd(k, p-1)$: the number of cycles is a greatest common divisor, its parity is the parity of $k$ because $p-1$ is even, and the parity of $k$ is whether the residue is a square. Three different-looking parities, and all of them are the same one.

There is a small trap in the middle of that chain and it is worth flagging. It is not true in general that $\gcd(k, N)$ is odd exactly when $k$ is odd; it is true when $N$ is even, which is the only case here. For an odd modulus of the group — which cannot happen for a prime $p > 2$ — the argument would collapse, and the collapse is the same one that makes the whole subject about odd primes.

Two ways to compute a sign, and why both are needed #

The sign of a permutation can be had from its cycles, as above, or by counting crossings in a drawing of it — how many pairs of strings cross when the two rows are laid out in order. The two agree, and the agreement is not trivial: the crossing count depends on how the strings are drawn and its parity does not.

Here the crossing count has a name. Laying out $0, 1, \ldots, p-1$ on both rows and joining $x$ to $ax \bmod p$, the number of crossings is the number of pairs $x < y$ with $ax \bmod p > ay \bmod p$ — the inversions of the shuffle. So the Legendre symbol counts inversions modulo two, and the hero figure computes both and refuses to draw if they disagree.

That redundancy is deliberate. The cycle route is an argument and the inversion route is a measurement of the picture; agreeing, they certify that the drawing is of the permutation the argument is about. A figure whose strings were routed wrongly would still have a cycle structure, and only the second count would notice.

Reciprocity, from one rectangle riffled two ways #

The reason Zolotarev’s theorem is more than a curiosity is what it does next. Consider the residues modulo $pq$ for distinct odd primes $p$ and $q$, and lay them out in a $p \times q$ rectangle in two different ways: filling row by row, and filling column by column.

By the Chinese remainder theorem each residue modulo $pq$ is a pair — its residue modulo $p$ and its residue modulo $q$ — so both layouts are honest coordinate systems on the same set. The map from one layout to the other is a permutation of $pq$ things, and its sign can be computed directly: it is a riffle, and the count of its inversions is $\binom{p}{2}\binom{q}{2}$-ish in a way that reduces to $(-1)^{\frac{p-1}{2}\cdot\frac{q-1}{2}}$.

On the other hand, that same permutation factors through the multiplication maps: reading the rectangle one way and then the other is multiplication by $q$ on one factor and by $p$ on the other, so its sign is $\left(\frac{q}{p}\right)\left(\frac{p}{q}\right)$ by the theorem above.

Setting the two computations of one sign equal gives

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

which is the law. The whole proof is one object counted two ways — which is the same shape as the lattice-point argument and a completely different object.

What the two proofs have in common, and what they do not #

The Eisenstein proof counts lattice points under a diagonal; this one counts inversions of a shuffle. Both end in the exponent $\frac{p-1}{2}\cdot\frac{q-1}{2}$, and both get there by counting one thing two ways.

What differs is what they generalise to. The lattice count is geometric and its natural extension is to other lattices and other slopes — which is how it reaches Dedekind sums and the reciprocity of certain finite sums. Zolotarev’s is algebraic: it says the Legendre symbol is a sign character, a homomorphism from the residues to $\{\pm 1\}$ realised inside the symmetric group, and its natural extension is to other groups and other transfer maps. The modern statement is that the symbol is a transfer homomorphism, and Zolotarev’s rectangle is the smallest instance of a general construction.

Neither generalisation is visible from inside the other proof, which is the reason a theorem accumulates proofs rather than settling on one.

Who found it, and how long it stayed lost #

Yegor Zolotarev published the argument in 1872, three-quarters of a century after Gauss’s first proof, in a paper whose main subject was something else — the theory of ideal numbers in quadratic fields. The reciprocity proof is a few pages of it, and it was not the point.

It then had a curious afterlife. The result is short, elementary, requires nothing but the cyclic structure of the residues, and would fit on a page of any undergraduate course — and it is absent from most of them. Frobenius rediscovered essentially the same argument in 1914, and the modern group-theoretic reading, in which the symbol is a transfer map, arrived later still and made it look inevitable in retrospect.

A proof can be short, correct, and still fail to circulate, and the usual reason is the one operating here: it does not fit the shape of the surrounding course. A first course in number theory reaches reciprocity before it has said anything about permutation signs, and a first course in algebra reaches permutation signs with no reason to care about residues. The proof sits in the gap between two syllabuses and belongs to neither.

Which is a decent argument for a collection organised by argument rather than by subject. The two halves of Zolotarev’s proof are on this site already and were written years apart in its own terms — the sign of a rearrangement in algebra and the rectangle counted twice in number theory — and the essay joining them is this one.

The Jacobi symbol comes along for free #

Zolotarev’s statement does not need $p$ prime. Multiplication by $a$ is a permutation of the residues modulo any $n$ coprime to $a$, that permutation has a sign, and the sign turns out to be the Jacobi symbol $\left(\frac{a}{n}\right)$ — the product of the Legendre symbols over the prime factors of $n$, counted with multiplicity.

The proof is the multiplicativity of the sign under the Chinese remainder decomposition: splitting $\mathbb{Z}/n$ into its prime-power factors splits the permutation into a product, and signs multiply.

That is a genuinely stronger statement, and it explains a fact about the Jacobi symbol that otherwise looks like a bookkeeping accident: the symbol is defined as a product over prime factors and yet obeys reciprocity as though it were a single Legendre symbol. It obeys reciprocity because it is the sign of a shuffle, and shuffles do not know how the modulus factors.

What a sign character is, once it has been seen twice #

Having found the symbol inside the symmetric group, it is worth asking what kind of object has been found, because the answer is what the modern proof is a statement about.

A homomorphism from a group to $\{+1, -1\}$ is a way of splitting the group into two halves, one of them a subgroup of index two. The residues modulo $p$ have exactly one such splitting, into squares and non-squares, because the group is cyclic of even order and a cyclic group has exactly one subgroup of each order dividing it. The symmetric group on $n$ letters also has exactly one, into even and odd permutations, for a quite different reason — because its commutator subgroup is the alternating group.

Zolotarev’s theorem says one of those splittings pulls back to the other. The map $a \mapsto \pi_a$ embeds the residues into the symmetric group on $p$ letters; the sign character on the big group restricts to a character on the small one; and since the small group has only one non-trivial character to $\{\pm 1\}$, the restriction is either trivial or the Legendre symbol. Checking one generator settles which, and the four-line argument above is exactly that check.

That reformulation costs nothing and buys the Jacobi extension immediately, because the uniqueness argument never used primality — only that the group of units has even order and a unique index-two subgroup in each factor. It also names what to look for elsewhere: a group embedded in a bigger one whose sign character restricts to something arithmetically meaningful. The general machine is called the transfer, and this is its smallest interesting output.

Where it fails, and what it needs #

The multiplier must be invertible. If $\gcd(a, n) > 1$ then $x \mapsto ax$ is not a permutation — it collapses — and there is no sign to speak of. That matches the symbol, which is defined to be zero in exactly that case, but the match is a convention rather than a theorem: zero is not a sign.

The cyclic structure is doing real work. The four-line proof above uses that the non-zero residues modulo a prime form a cyclic group, which is itself a theorem and not a small one. Zolotarev’s argument is short because it is standing on that; the lattice-point proof stands on nothing beyond counting.

And the sign is a statement about the whole permutation. It cannot be localised: there is no sense in which some residues contribute more than others. That is what makes the symbol so useful and so uninformative at once — it answers one bit and refuses every follow-up question, such as which residue actually squares to $a$.

What the pictures cannot show #

A drawing of a shuffle grows unmanageable fast. At $p = 11$ the strings are readable; at $p = 101$ they are a grey band. Every claim here is about all $p$, and the pictures are at the largest size a picture can still be read at.

The rectangle argument is drawn only for one pair. The grid figure shows fifteen residues in two orderings. The general statement is about all pairs of odd primes, and the count of inversions that produces the exponent is arithmetic that happens off the page.

And nothing here shows the sign being well defined. That a permutation has a sign at all is the theorem the crossings essay exists to prove, and everything above assumes it. A figure of this page’s kind takes it for granted, which is the right division of labour and worth saying out loud.

Where the ladder goes next #

The next rung leaves counting behind entirely. The Gauss sum adds the $p$-th roots of unity with the Legendre symbol as the sign on each, and squaring the result gives $\pm p$ — an identity in the complex numbers whose evaluation two ways is the law again. That is the proof that generalises furthest, and it is the first one on this ladder to leave the integers.

Sideways: the polygon the roots of unity make is where the next rung’s object lives, and the cyclic structure of the residues is what this rung leaned on throughout.

What is worth carrying away #

A quantity defined by one construction can turn out to be computed by a completely different one, and when that happens the two constructions inherit each other’s theorems.

The Legendre symbol was defined to answer whether something is a square. The sign of a permutation was defined to make determinants well defined. Neither definition mentions the other and they coincide, which means every fact about permutation signs is now a fact about squares modulo $p$ — including the one that matters here, that a sign can be computed by counting a rectangle two ways.

The general move is to look for a second definition of a quantity that already has one. It is rarely available and it is worth a great deal when it is, because the two definitions almost never generalise in the same direction.