Quadratic reciprocity and Zolotarev’s Lemma

I want to explain a beautiful proof of the Law of Quadratic Reciprocity from c. 1874 due to Egor Ivanovich Zolotarev (1847-1878). Some time ago I reformulated Zolotarev’s argument (as presented here) in terms of dealing cards and I posted a little note about it on my web page. After reading my write-up (which was unfortunately opaque in a couple of spots), Jerry Shurman was inspired to rework the argument and he came up with this elegant formulation which I think may be a “proof from the book”.  The following exposition is my own take on Jerry’s argument.  The proof requires some basic facts about permutations, all of which are proved in this handout.

Let m and n be odd relatively prime positive integers.  You have a stack of mn playing cards numbered 0 through mn-1 and you want to deal them onto the table in an m \times n rectangular array.  Consider the following three ways of doing this:

Row deal (\rho) : Deal the cards into rows, going left to right and top to bottom.

rho

Column deal (\kappa): Deal the cards into columns, going top to bottom and left to right.

kappa

Diagonal deal (\delta): Deal the cards diagonally down and to the right, wrapping around from bottom to top or right to left whenever necessary.

delta

There are corresponding actions which undo the above deals, which we will denote by Row pickup (\rho^{-1}), Column pickup (\kappa^{-1}), and Diagonal pickup (\delta^{-1}). Note that in a pickup move each successive card is placed under the previous one.

We combine these basic moves as follows, obtaining three different permutations of the rectangular array which we denote by \alpha, \beta, and \gamma:

\alpha = \delta \circ \rho^{-1} is a row pickup followed by a diagonal deal.

\beta = \delta \circ \kappa^{-1} is a column pickup followed by a diagonal deal.

\gamma = \kappa \circ \rho^{-1} is a row pickup followed by a column deal.

For later use, we note that \alpha permutes each column separately and \beta permutes each row separately.  (Try it with actual cards and you will easily convince yourself of this!)

It is clear that \alpha = \beta \circ \gamma, i.e., doing \gamma and then \beta is the same as doing \alpha.  Since the sign of a permutation is a homomorphism, we have {\rm sign}(\alpha) = {\rm sign}(\beta) \cdot {\rm sign}(\gamma).  Believe it or not, this self-evident observation is the Law of Quadratic Reciprocity in disguise!

Let me explain.

Claim 1: {\rm sign}(\alpha) is equal to the sign of the permutation of the integers modulo m induced by multiplication by n, which we write as \left[ \frac{n}{m} \right].  (By symmetry, we have {\rm sign}(\beta) = \left[ \frac{m}{n} \right].)

Claim 2: {\rm sign}(\gamma) = (-1)^{\frac{(m-1)(n-1)}{4}}.

From these two claims, we obtain:

Zolotarev’s Reciprocity Law: If m and n are relatively prime odd positive integers, then

\left[ \frac{n}{m} \right] = (-1)^{\frac{(m-1)(n-1)}{4}} \left[ \frac{m}{n} \right].

The connection with Quadratic Reciprocity is via:

Zolotarev’s Lemma: If p is an odd prime and a is a positive integer not divisible by p, then \left[ \frac{a}{p} \right] = \left( \frac{a}{p} \right), where \left( \frac{a}{p} \right) denotes the Legendre symbol.

Combining Zolotarev’s Reciprocity Law and Zolotarev’s Lemma, we immediately obtain:

The Law of Quadratic Reciprocity: If p and q are distinct odd primes, then

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

We now explain how to prove the two claims, as well as Zolotarev’s Lemma.  For the explanation, it is helpful to identify the initial stack of cards with the set of integers \{ 0,1,2,\ldots, mn-1 \}.  Also, by indexing the rows of the array by 0,1,\ldots,m-1 and the columns by 0,1,\ldots,n-1, we can identify the array with the set {\mathbf Z}/m {\mathbf Z} \times {\mathbf Z}/n {\mathbf Z}.  In this way we can identify \rho, \kappa, and \delta with the following maps from \{ 0,1,2,\ldots, mn-1 \} to {\mathbf Z}/m {\mathbf Z} \times {\mathbf Z}/n {\mathbf Z} (where x \in \{ 0,1,\ldots,m-1 \} and y \in \{ 0,1,\ldots,n-1 \}):

\rho(nx+y) = (x {\rm \; mod \;} m, y {\rm \; mod \;} n),

\kappa(x+my) = (x {\rm \; mod \;} m, y {\rm \; mod \;} n),

\delta(z) = (z {\rm \; mod \;} m, z {\rm \; mod \;} n).

Proof of Claim 1: By the above formulas we have \alpha(x,y) = (nx+y,y) and \beta(x,y) = (x,x+my).  It follows that \alpha is the product of the n “column permutations” \alpha_y(x) \mapsto nx+y \pmod{m}.  But each \alpha_y is a composition of multiplication by n modulo m with the permutation x \mapsto x+y \pmod{m}, which always has sign +1 since it’s either trivial or a product of {\rm GCD}(y,m) cycles, each of length m/{\rm GCD}(y,m), and we’re assuming that m is odd.  Since n is odd as well, we obtain the claim about {\rm sign}(\alpha), and the corresponding assertion for \beta follows by symmetry.

Proof of Claim 2: The sign of a permutation \tau of a totally ordered finite set is equal to -1 to the number of inversions of \tau. (An inversion is a pair (a,b) with a < b and \tau(b) < \tau(a).)  We put the column-major order (the order depicted in the second figure above) on our array.  Note that for a,b in the array, \gamma(b) is less than \gamma(a) in column-major order if and only if b < a in row-major order (the order depicted in the first figure above).  So \{ a,b \} is an inversion pair in column-major order if and only if a is below and to the left of b.  The number of such inversion pairs is \binom{m}{2} \cdot \binom{n}{2}, since each pair of 2-element subsets \{ x,x' \} of \{0,1,\ldots,m\} and \{ y,y' \} of \{0,1,\ldots,n\} gives rise to a unique inversion (by ordering the elements a=(x,y),b=(x',y') so that x < x' and y' < y).  The claim follows since m and n are assumed to be odd.  (Note that we do not require m and n to be relatively prime for this argument.)

Proof of Zolotarev’s Lemma:

Let g be a primitive root modulo p, and write a \equiv g^k \pmod{p}.  Then the permutation of \{ 1,2,\ldots,p-1 \} given by multiplication by a modulo p has the same sign as the permutation of \{ 0,1,\ldots,p-2 \} given by x \mapsto x + k modulo p-1.  The latter is a product of k cycles, each of size (p-1)/k, so \left[ \frac{a}{p} \right] = \left( (-1)^{\frac{p-1}{k} - 1} \right)^k = (-1)^{p-1-k}.  It follows that \left[ \frac{a}{p} \right] = 1 if and only if k is even, which happens if and only if \left( \frac{a}{p} \right) = 1.

Concluding observations:

1) Zolotarev’s original paper can be downloaded here.

2) The supplement to the Law of Quadratic Reciprocity determining the Legendre symbol \left( \frac{2}{p} \right) is also easily deduced from Zolotarev’s Lemma, which shows that \left( \frac{2}{p} \right) is -1 to the number of inversions of multiplication by 2 modulo p.  A pair \{ a, b \} with a < b gets inverted if and only if 1 \leq a \leq (p-1)/2 and (p-1)/2 + 1 \leq b \leq (p-1)/2 + a.  Thus the number of inversions is 1+2+\cdots+(p-1)/2 = (p^2 - 1)/8, which by inspection is even if p is congruent to 1 or 7 modulo 8 and odd otherwise.

3) If we identify the set \{ 0,1,2,\ldots, mn-1 \} with the set {\mathbf Z} / mn {\mathbf Z} of integers modulo mn, the map \delta is just the canonical ring isomorphism from {\mathbf Z} / mn {\mathbf Z} to {\mathbf Z}/m {\mathbf Z} \times {\mathbf Z}/n {\mathbf Z} afforded by the Chinese Remainder Theorem.

4) An alternative, more algebraic argument, for Claim 2 is as follows.  Since the bijection \rho identifies the permutation \gamma = \kappa \rho^{-1} of the array with the permutation \lambda = \rho^{-1} \gamma \rho = \rho^{-1} \kappa of the totally ordered set \{ 0,1,2,\ldots, mn-1 \}, it suffices to compute the number of inversions of \lambda.  Using the explicit formula \lambda(x+my) = nx+y we see that inversions of \lambda correspond to ordered pairs (x,y), (x',y'), with x,x' \in \{ 0,1,\ldots,m-1 \} and y,y' \in \{ 0,1,\ldots,n-1 \}, such that x+my < x'+my' and nx'+y' < nx+y.  The latter two conditions together are easily seen to be equivalent to x < x' and y' < y.

5) A more group-theoretic proof of Zolotarev’s Lemma is as follows.  We observe that \left[ \frac{\cdot}{p} \right] is a surjective homomorphism from ({\mathbf Z} / p{\mathbf Z})^\times to \{ \pm 1 \}; surjectivity follows from the fact that if g is a primitive root mod p (i.e., a cyclic generator of ({\mathbf Z} / p{\mathbf Z})^\times) then \left[ \frac{g}{p} \right] is a (p-1)-cycle and thus has signature -1.  The kernel of \left[ \frac{\cdot}{p} \right] is therefore a subgroup of ({\mathbf Z} / p{\mathbf Z})^\times of index 2, but the only such subgroup is the group of quadratic residues.  Thus \left[ \frac{\cdot}{p} \right] coincides with the Legendre symbol \left( \frac{\cdot}{p} \right).

6) Zolotarev’s Lemma generalizes to the statement that if m,n are relatively prime odd positive integers then \left[ \frac{m}{n} \right] is equal to the Jacobi symbol \left( \frac{m}{n} \right), and the proof above then gives quadratic reciprocity for the Jacobi symbol (which is used for rapid computation of Legendre symbols).  Note that in general \left[ \frac{m}{n} \right] is the sign of multiplication by m on {\mathbf Z} / n{\mathbf Z} and not on ({\mathbf Z} / n{\mathbf Z})^\times, though when n is prime these coincide.

[Updated November 26, 2013.]

7 thoughts on “Quadratic reciprocity and Zolotarev’s Lemma

  1. Hi Matt,

    I’m happy to see the growing popularity of Zolotarev’s proof! When I teach it, I use the following approach/notation (and this will appear in my Illustrated Theory of Numbers book eventually). It’s not as magic-tricky as the card deal, but the notation is useful for other parts of teaching number theory.

    Fix two odd primes p and q throughout. Let a be an integer between 0 and p-1 and b an integer between 0 and q-1. Let S be the set of integers between 0 and pq-1. Define:

    [a,b] to be the unique element of S congruent to a modulo p and b modulo q;

    [a,b> to be the integer bp + a; (note that [a,b> is congruent to a, modulo p. Hence the bracket agreeing with [a,b] on the a-side)

    <a,b] to be the integer aq+b. (same comment as before).

    Now the three permutations of S are:

    L sends [a,b] to

    F (flip) sends .

    I find this approach works really well, especially if the notation [a,b] is introduced earlier in the context of the Chinese remainder theorem. Besides the notation, I think my usual approach is the same proof as yours (and Zolotarev’s).

    Reply
    • Uh oh – I think my plaintext math was interpreted as an HTML link. Sorry about that! You might guess that L sends [a,b] to \langle a,b] and R sends [a,b] to [a,b \rangle and F sends \langle a,b] to [a,b \rangle.

      Whoops!

      Reply
  2. Pingback: Quadratic reciprocity | eon

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s