Zolotarev’s lemma

We will identify the ring n of integers modulo n, with the set {0,1,n-1}.

Lemma 1 (Zolotarev).

For any prime numberMathworldPlanetmath p and any mZp*, the Legendre symbolMathworldPlanetmath (mp) is equal to the signaturePlanetmathPlanetmathPlanetmath (http://planetmath.org/SignatureOfAPermutation) of the permutationMathworldPlanetmath τm:xmx of Zp*.


We write ϵ(σ) for the signature of any permutation σ. If σ is a circular permutation on a set of k elements, then ϵ(σ)=(-1)k-1. Let i be the order of m in p*. Then the permutation τm consists of (p-1)/i orbits, each of size i, whence


If i is even, then


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


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

Lemma 1 extends easily from the Legendre symbol to the Jacobi symbolMathworldPlanetmath (mn) for odd n. The following is Zolotarev’s penetrating proof of the quadratic reciprocity law, using Lemma 1.

Lemma 2.

Let λ be the permutation of the set


which maps the kth element of the sequenceMathworldPlanetmath


to the kth element of the sequence


for every k from 1 to mn. Then


and if m and n are both odd,


We will use the fact that the signature of a permutation of a finite totally ordered setMathworldPlanetmath is determined by the number of inversions of that permutation. The sequence (0,0),(0,1) defines on Amn a total order in which the relationMathworldPlanetmath (i,j)<(i,j) means

i<i or (i=i and j<j).

But λ(i,j)<λ(i,j) means

j<j or (j=j and i<i).

The only pairs ((i,j),(i,j)) that get inverted are, therefore, the ones with i<i and j>j. There are indeed (m2)(n2) such pairs, proving the first formulaMathworldPlanetmathPlanetmath, and the second follows easily. ∎

And finally, we proceed to prove quadratic reciprocity. Let p and q be distinct odd primes. Denote by π the canonical ring isomorphismPlanetmathPlanetmathPlanetmathPlanetmath pqp×q. Define two permutations α and β of p×q by α(x,y)=(qx+y,y) and β(x,y)=(x,x+py). Finally, define a map λ:pqpq by λ(x+qy)=px+y for x{0,1,q-1} and y{0,1,p-1}. Evidently λ is a permutation.

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


Let us compare the signatures of the two sides. The permutation mqx+y is the compositionMathworldPlanetmathPlanetmath of mqx and mm+y. The latter has signature 1, whence by Lemma 1,


and similarly


By Lemma 2,




which is the quadratic reciprocity law.


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