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.

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

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

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 $\{ 1,2,\ldots,p-1 \}$ given by $x \mapsto x + k$ modulo $p-1$ . The latter is a product of $c:= {\rm GCD}(k,p-1)$ cycles, each of length $\ell := (p-1)/{\rm GCD}(k,p-1)$ , so $\left[ \frac{a}{p} \right] =(-1)^{c(\ell - 1)}.$ If $c$ is even then $c(\ell - 1)$ is also even, and if $c$ is odd then since $p$ is odd and $\ell c = p-1$ , $\ell$ must be even and hence $c(\ell - 1)$ is odd. Note also that $c$ is even if and only if $k$ is even. 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.]

10 thoughts on “Quadratic reciprocity and Zolotarev’s Lemma”

martyweissman says:

July 3, 2013 at 11:41 pm

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).

- martyweissman says:
  
  July 3, 2013 at 11:44 pm
  
  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!
  
mbakermath says:

July 3, 2013 at 11:57 pm

Hi Marty — Yes that also seems like a good way to present the proof. Looking forward to your Illustrated Theory of Numbers book!

galoisrepresentations says:

July 4, 2013 at 12:46 am

Wait – surely the proof using class field theory is the “proof from the book”?

- mbakermath says:
  
  July 4, 2013 at 4:46 am
  
  I was pretty careful to say a proof from the book and not the proof from the book.
  
galoisrepresentations says:

July 4, 2013 at 6:35 pm

Yes, I did see that, I was only being cheeky. Then again, wars have been fought over questions less significant than “what is the best proof of quadratic reciprocity?”

Pingback: Quadratic reciprocity | eon
Pingback: The Sign of the Quadratic Gauss Sum and Quadratic Reciprocity | Matt Baker's Math Blog
Pingback: Why did they prove this amazing theorem in 200 different ways? Quadratic Reciprocity MASTERCLASS – Burkard Polster – Divagaciones en el Cinosargo
Pingback: Quadratic Reciprocity via Lucas Polynomials | Matt Baker's Math Blog

Matt Baker's Math Blog

Thoughts on number theory, graphs, dynamical systems, tropical geometry, pedagogy, puzzles, and the p-adics

Quadratic reciprocity and Zolotarev’s Lemma

10 thoughts on “Quadratic reciprocity and Zolotarev’s Lemma”

Leave a reply to mbakermath Cancel reply

Share this:

Related

10 thoughts on “Quadratic reciprocity and Zolotarev’s Lemma”

Leave a reply to mbakermath Cancel reply