Zolotarev’s lemma

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

Lemma 1 (Zolotarev).

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

Proof.

We write $ϵ(\sigma )$ for the signature of any permutation $\sigma$. If $\sigma$ is a circular permutation on a set of $k$ elements, then $ϵ(\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

$$ϵ({\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}}=ϵ({\tau }_m)$$

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

$$m^{(p-1)/2}=m^{i\frac{p-1}{2i}}=1=ϵ({\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,\mathrm{\dots },m-1\}\times \{0,1,\mathrm{\dots },n-1\}$$

which maps the $k$th element of the sequence

$$(0,0)(0,1)\mathrm{\dots }(0,n-1)(1,0)\mathrm{\dots }(1,n-1)(2,0)\mathrm{\dots }(m-1,n-1),$$

to the $k$th element of the sequence

$$(0,0)(1,0)\mathrm{\dots }(m-1,0)(0,1)\mathrm{\dots }(m-1,1)(0,2)\mathrm{\dots }(m-1,n-1),$$

for every $k$ from $\mathrm{1}$ to $m\mathit{}n$. Then

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

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

$$ϵ(\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)\mathrm{\dots }$ defines on $A_{mn}$ a total order $\le$ in which the relation means

But means

The only pairs $((i,j),(i^{\prime },j^{\prime }))$ that get inverted are, therefore, the ones with and $j>j^{\prime }$. There are indeed $\left(\genfrac{}{}{0pt}{}{m}{2}\right)\left(\genfrac{}{}{0pt}{}{n}{2}\right)$ 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,\mathrm{\dots }q-1\}$ and $y\in \{0,1,\mathrm{\dots }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,

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

and similarly

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

By Lemma 2,

$$ϵ(\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