Zolotarev’s lemma

We will identify the ring $\mathbb{Z}_{n}$ of integers modulo $n$ , with the set $\{0,1,\ldots n-1\}$ .

Lemma 1 (Zolotarev).

For any prime number $p$ and any $m\in\mathbb{Z}_{p}^{*}$ , the Legendre symbol $\left(\frac{m}{p}\right)$ is equal to the signature (http://planetmath.org/SignatureOfAPermutation) of the permutation $\tau_{m}:x\mapsto mx$ of $\mathbb{Z}_{p}^{*}$ .

Proof.

We write $\epsilon(\sigma)$ for the signature of any permutation $\sigma$ . If $\sigma$ is a circular permutation on a set of $k$ elements, then $\epsilon(\sigma)=(-1)^{k-1}$ . Let $i$ be the order of $m$ in $\mathbb{Z}_{p}^{*}$ . Then the permutation $\tau_{m}$ consists of $(p-1)/i$ orbits, each of size $i$ , whence

\epsilon(\tau_{m})=(-1)^{(i-1)(p-1)/i}

If $i$ is even, then

m^{(p-1)/2}=m^{\frac{i}{2}\frac{p-1}{i}}=(-1)^{\frac{p-1}{i}}=\epsilon(\tau_{m})

And if $i$ is odd, then $2i$ divides $p-1$ , so

m^{(p-1)/2}=m^{i\frac{p-1}{2i}}=1=\epsilon(\tau_{m}).

In both cases, the lemma follows from Euler’s criterion. ∎

Lemma 1 extends easily from the Legendre symbol to the Jacobi symbol $\left(\frac{m}{n}\right)$ for odd $n$ . The following is Zolotarev’s penetrating proof of the quadratic reciprocity law, using Lemma 1.

Lemma 2.

Let $\lambda$ be the permutation of the set

A_{mn}=\{0,1,\ldots,m-1\}\times\{0,1,\ldots,n-1\}

which maps the $k$ th element of the sequence

(0,0)(0,1)\ldots(0,n-1)(1,0)\ldots(1,n-1)(2,0)\ldots(m-1,n-1),

to the $k$ th element of the sequence

(0,0)(1,0)\ldots(m-1,0)(0,1)\ldots(m-1,1)(0,2)\ldots(m-1,n-1),

for every $k$ from $1$ to $m n$ . Then

\epsilon(\lambda)=(-1)^{m(m-1)n(n-1)/4}

and if $m$ and $n$ are both odd,

\epsilon(\lambda)=(-1)^{(m-1)(n-1)/4}.

Proof.

We will use the fact that the signature of a permutation of a finite totally ordered set is determined by the number of inversions of that permutation. The sequence $(0,0),(0,1)\ldots$ defines on $A_{mn}$ a total order $\leq$ in which the relation $(i,j)<(i^{\prime},j^{\prime})$ means

i<i^{\prime}\text{ or }(i=i^{\prime}\text{ and }j<j^{\prime}).

But $\lambda(i^{\prime},j^{\prime})<\lambda(i,j)$ means

j^{\prime}<j\text{ or }(j^{\prime}=j\text{ and }i^{\prime}<i).

The only pairs $((i,j),(i^{\prime},j^{\prime}))$ that get inverted are, therefore, the ones with $i<i^{\prime}$ and $j>j^{\prime}$ . There are indeed $\binom{m}{2}\binom{n}{2}$ such pairs, proving the first formula, and the second follows easily. ∎

And finally, we proceed to prove quadratic reciprocity. Let $p$ and $q$ be distinct odd primes. Denote by $\pi$ the canonical ring isomorphism $\mathbb{Z}_{pq}\to\mathbb{Z}_{p}\times\mathbb{Z}_{q}$ . Define two permutations $\alpha$ and $\beta$ of $\mathbb{Z}_{p}\times\mathbb{Z}_{q}$ by $\alpha(x,y)=(qx+y,y)$ and $\beta(x,y)=(x,x+py).$ Finally, define a map $\lambda:\mathbb{Z}_{pq}\to\mathbb{Z}_{pq}$ by $\lambda(x+qy)=px+y$ for $x\in\{0,1,\ldots q-1\}$ and $y\in\{0,1,\ldots p-1\}$ . Evidently $\lambda$ is a permutation.

Note that we have $\pi(qx+y)=(qx+y,y)$ and $\pi(x+py)=(x,x+py)$ , so therefore

\pi\circ\lambda\circ\pi^{-1}\circ\alpha=\beta.

Let us compare the signatures of the two sides. The permutation $m\mapsto qx+y$ is the composition of $m\mapsto qx$ and $m\mapsto m+y$ . The latter has signature $1$ , whence by Lemma 1,

\epsilon(\alpha)=\left(\frac{q}{p}\right)^{q}=\left(\frac{q}{p}\right)

and similarly

\epsilon(\beta)=\left(\frac{p}{q}\right)^{p}=\left(\frac{p}{q}\right).

By Lemma 2,

\epsilon(\pi\circ\lambda\circ\pi^{-1})=(-1)^{(p-1)(q-1)/4}.

Thus

(-1)^{(p-1)(q-1)/4}\left(\frac{q}{p}\right)=\left(\frac{p}{q}\right)

which is the quadratic reciprocity law.

Reference

G. Zolotarev, Nouvelle démonstration de la loi de réciprocité de Legendre, Nouv. Ann. Math (2), 11 (1872), 354-362

Title	Zolotarev’s lemma
Canonical name	ZolotarevsLemma
Date of creation	2013-03-22 13:28:25
Last modified on	2013-03-22 13:28:25
Owner	mathcam (2727)
Last modified by	mathcam (2727)
Numerical id	15
Author	mathcam (2727)
Entry type	Theorem
Classification	msc 11A15
Related topic	GaussLemma