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.
Let and be odd relatively prime positive integers. You have a stack of playing cards numbered 0 through and you want to deal them onto the table in an rectangular array. Consider the following three ways of doing this:
Row deal () : Deal the cards into rows, going left to right and top to bottom.
Column deal (): Deal the cards into columns, going top to bottom and left to right.
Diagonal deal (): 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 (), Column pickup (), and Diagonal pickup (). 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 , , and :
is a row pickup followed by a diagonal deal.
is a column pickup followed by a diagonal deal.
is a row pickup followed by a column deal.
For later use, we note that permutes each column separately and permutes each row separately. (Try it with actual cards and you will easily convince yourself of this!)
It is clear that , i.e., doing and then is the same as doing . Since the sign of a permutation is a homomorphism, we have . Believe it or not, this self-evident observation is the Law of Quadratic Reciprocity in disguise!
Let me explain.
Claim 1: is equal to the sign of the permutation of the integers modulo induced by multiplication by , which we write as . (By symmetry, we have .)
From these two claims, we obtain:
Zolotarev’s Reciprocity Law: If and are relatively prime odd positive integers, then
The connection with Quadratic Reciprocity is via:
Zolotarev’s Lemma: If is an odd prime and is a positive integer not divisible by , then , where denotes the Legendre symbol.
Combining Zolotarev’s Reciprocity Law and Zolotarev’s Lemma, we immediately obtain:
The Law of Quadratic Reciprocity: If and are distinct odd primes, then
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 . Also, by indexing the rows of the array by and the columns by , we can identify the array with the set . In this way we can identify , , and with the following maps from to (where and ):
Proof of Claim 1: By the above formulas we have and . It follows that is the product of the “column permutations” . But each is a composition of multiplication by modulo with the permutation , which always has sign since it’s either trivial or a product of cycles, each of length , and we’re assuming that is odd. Since is odd as well, we obtain the claim about , and the corresponding assertion for follows by symmetry.
Proof of Claim 2: The sign of a permutation of a totally ordered finite set is equal to to the number of inversions of . (An inversion is a pair with and .) We put the column-major order (the order depicted in the second figure above) on our array. Note that for in the array, is less than in column-major order if and only if in row-major order (the order depicted in the first figure above). So is an inversion pair in column-major order if and only if is below and to the left of . The number of such inversion pairs is , since each pair of 2-element subsets of and of gives rise to a unique inversion (by ordering the elements so that and ). The claim follows since and are assumed to be odd. (Note that we do not require and to be relatively prime for this argument.)
Proof of Zolotarev’s Lemma:
Let be a primitive root modulo , and write . Then the permutation of given by multiplication by modulo has the same sign as the permutation of given by modulo . The latter is a product of cycles, each of size , so . It follows that if and only if is even, which happens if and only if .
1) Zolotarev’s original paper can be downloaded here.
2) The supplement to the Law of Quadratic Reciprocity determining the Legendre symbol is also easily deduced from Zolotarev’s Lemma, which shows that is to the number of inversions of multiplication by 2 modulo . A pair with gets inverted if and only if and . Thus the number of inversions is , which by inspection is even if is congruent to 1 or 7 modulo 8 and odd otherwise.
3) If we identify the set with the set of integers modulo , the map is just the canonical ring isomorphism from to afforded by the Chinese Remainder Theorem.
4) An alternative, more algebraic argument, for Claim 2 is as follows. Since the bijection identifies the permutation of the array with the permutation of the totally ordered set , it suffices to compute the number of inversions of . Using the explicit formula we see that inversions of correspond to ordered pairs , with and , such that and . The latter two conditions together are easily seen to be equivalent to and .
5) A more group-theoretic proof of Zolotarev’s Lemma is as follows. We observe that is a surjective homomorphism from to ; surjectivity follows from the fact that if is a primitive root mod (i.e., a cyclic generator of ) then is a -cycle and thus has signature . The kernel of is therefore a subgroup of of index 2, but the only such subgroup is the group of quadratic residues. Thus coincides with the Legendre symbol .
6) Zolotarev’s Lemma generalizes to the statement that if are relatively prime odd positive integers then is equal to the Jacobi symbol , 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 is the sign of multiplication by on and not on , though when is prime these coincide.
[Updated November 26, 2013.]