# 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 $mn$. 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

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

 $j^{\prime}

The only pairs $((i,j),(i^{\prime},j^{\prime}))$ that get inverted are, therefore, the ones with $i 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 ZolotarevsLemma 2013-03-22 13:28:25 2013-03-22 13:28:25 mathcam (2727) mathcam (2727) 15 mathcam (2727) Theorem msc 11A15 GaussLemma