Zolotarev's Lemma and Quadratic Reciprocity

The law of quadratic reciprocity is unquestionably one of the most famous results of mathematics. Carl Gauss, often called the "Prince of Mathematicians", referred to it as "The Golden Theorem". He published six proofs of it in his lifetime. To date over 200 proofs of this result have been found. The single most frustrating thing about this theorem is that there are no easy proofs of it, at least when measured relative to the simplicity of the statement and the mathematics it involves. For someone like myself, who prides themselves on being able to find very slick proofs, it can drive you insane. As an undergraduate, when confronted with the lattice-point proof in an introductory number theory class, I refused to learn it. I thought to myself there's no way I need to go through all that just to prove something so simple. There must be an easier way. Zolotarev's Proof of the law has been to date the simplest, and quite frankly most elegant, proof that I can find. The crucial step involves equating the value of the Legendre symbol with the signature of the permutation on $\mathbb{Z}_q$ induced by left multiplication. It can take a little bit longer going through it the first time, but winds up being one of those proofs you can just remember without needing to re-reference it. I had a difficult time finding the result from a single source, at least in a satisfactory form, and had to compile different results from different sources. I thought others might similarly struggle, and so I've typed it below as a resource for them.

Zolotarev's Lemma relates the value of the Legendre symbol to the signature of a permutation of $\mathbb{Z}_p$ It is stated and proved below, along with its use in what is considered to be a very elegant proof of the quadratic reciprocity law.

Zolotarev's Lemma: Let $p$ be an odd prime, $a \in \mathbb{Z}_p^\times $, and $\tau_a : \mathbb{Z_p} \to \mathbb{Z_p}$ be the permutation of $\mathbb{Z_p}$ given by $\tau_a(x):= ax, \,$ then

$$\binom{a}{p} = \text{sgn}(\tau_a) $$

Proof:

We determine the signature based on the parity of the cycle structure. Note that the signature of a k-cycle is $(-1)^{k-1}$. Let $m = |a|$ in $\mathbb{Z}_p^\times$. Since $0$ is a singleton orbit (i.e. fixed point) of $\tau_a$, and therefore has no effect on its signature, it suffices to proof this for the restriction of $\tau_a$ to $\mathbb{Z}_p^\times$, as the signature will be the same for both. Each cycle has the form $(x,ax,a^2x,a^3x,\dots ,a^{m-1}x)$. Thus the cycle structure consists of $(p-1)/m \ $ $\ m$-cycles, and its signature is therefore given by:

$ \\ $

$$ \text{sgn}(\tau_a)= \left((-1)^{m-1}\right)^{p-1 \over m} = \begin{cases} (-1)^{\frac{p-1}{m}} & \mathrm{if} \ m \text{ is even} \\ \\ \ \ \ 1 & \text{if } m \text{ is odd} \end{cases} $$

$ \\ $

Recall that $x^2 = 1 \; (\text{mod }p) \implies x = \pm 1 \; (\text{mod }p)$, and thus $a^{m/2} = -1 \:$ as $ \ \frac{m}{2} < m = |a| $. If $m$ is even we have $$ a^{\frac{p-1}{2}} = \left(a^{\frac{m}{2}}\right)^{\frac{p-1}{m}} = (-1)^{\frac{p-1}{m}} = \text{sgn}(\tau_a)$$

$ \\ $

If $m$ is odd, then $(2,m) = 1 \text{ and } 2,m \,\big| \, p\!-\!1 \implies 2m \, \big| \, p\!-\!1 $ and we have:

$$a^{\frac{p-1}{2}} = \left(a^m \right)^\frac{p-1}{2m} = 1^{\frac{p-1}{2m}} = 1 = \text{sgn}(\tau_a)$$

$ \\ $

Euler's criterion then finishes the argument.

$ \\ $

Corollary: If p and q are odd primes, $a \in \mathbb{Z}_q$, and $b \in \mathbb{Z}_p $ then $\binom{q}{p}$ and $\binom{p}{q}$ are equal to the signatures of the permutations $x \mapsto qx + b $ and $x \mapsto a + px$ respectively.

$ \\ $

Proof

The argument is symmetric. We shall prove it for $\binom{p}{q}$. Let $ a \in \mathbb{Z}_q$ and define the permutation $\sigma: \mathbb{Z}_q \to \mathbb{Z}_q$ by $\sigma(x):= a + x$. If $ a = 0$, then $\sigma = Id$ and $\text{sgn}(\sigma) = 1$. Otherwise, the permutation consists of a single p-cycle, $(x,a+x,2a+x,\dots,(q-1)a+x)$ and thus sgn$(\sigma) = 1$ also. Letting $\tau_p$ be as defined above, the permutation $x \to a+px$ is equal to the composition $\sigma \tau_p$ and thus by Zolotarev's Lemma its signature is $\text{sgn}(\sigma \tau_p) = \text{sgn}(\sigma)\text{sgn}(\tau_p) = \text{sgn}(\tau_p) = \binom{p}{q}$.

$ \\ $

The Law of Quadratic Reciprocity: If $p$ and $q$ are odd primes then $$\binom{p}{q} \binom{q}{p} = (-1)^{\frac{p-1}{2} \frac{q-1}{2}}$$

Proof

Let $\tau: \mathbb{Z}_{pq} \to \mathbb{Z}_p \times \mathbb{Z}_q \ \text{ and } \ \lambda,\alpha : \mathbb{Z}_p \times \mathbb{Z}_q \to \mathbb{Z}_p \times \mathbb{Z}_q$ be permutations defined as follows:

$$ \begin{align} \tau(x):=& \ (x,x) \\ \lambda(a,b):=& \ \left(a,a\!+\!p{}b\right) \\ \alpha(a,b):=& \ \left(q{}a\!+\!b,b\right) \end{align} $$

Now define the permutation $\varphi: \mathbb{Z}_{pq} \to \mathbb{Z}_{pq}$ by the rule $\varphi(a+pb):= qa+b$. This function is well-defined by the Division Algorithm, provided we view it as being defined only on the residues. It is routine to extend this argument to account for the congruence classes in general.

Note that $\varphi = \tau^{-1} \circ \alpha \lambda^{-1}\! \circ \tau$ and thus $\text{sgn}(\varphi) = \text{sgn}(\alpha)\text{sgn}(\lambda)$

We count the signature of $\varphi$ in two ways - by its cycle parity and then by its inversions. Looking at $\lambda$'s cycle structure, we note that for each $a \in \mathbb{Z_p}$ the restriction of $\lambda$ to $\{a\} \times \mathbb{Z}_q$ is still a permutation, and its cycle structure is identical to the cycle structure of the permutation $b \mapsto a+pb$ it induces in its second coordinate. In particular the restriction of $\lambda$ to $\{a\} \times \mathbb{Z}_q$ has a signature equal to $\binom{p}{q}$. We can then extend this function to the rest of $\mathbb{Z}_p \times \mathbb{Z}_q$ by making it the identity, and we can then view $\lambda$ as the p-fold composition of these permutations, and thus $\text{sgn}(\lambda) = \binom{p}{q}^p = \binom{p}{q}$. It is best to see this via an example.Similarly, $\text{sgn}(\alpha) = \binom{q}{p}$ and thus $$\text{sgn}(\varphi) = \binom{p}{q}\binom{q}{p}$$

We now count the inversions. Note that $$a_1 + p{}b_1 < a_2 +p{}b_2 \text{ and }q{}a_2+b_2 < q{}a_1+b_1 \implies a_1 - a_2 < p(b_2 - b_1) < p{}q(a_1 - a_2)$$

Since $a_1 - a_2$ gets larger when multiplied by the positive integer $pq$ we must have that $a_1 - a_2 > 0$ which then forces $b_2 - b_1 > 0$. It can also be seen that this is a sufficient condition for an inversion as well. Thus the pair $\left(a_1 + pb_1,a_2+pb_2 \right)$ represents an inversion under $\varphi$ if and only if $a_1 > a_2 \text{ and } b_2 > b_1$. Since given any pair of distinct integers one is necessarily larger than the other, any pair of doubles $(a_1,a_2),(b_1,b_2)$ corresponds to a unique inversion,provided we don't distinguish between $(a_1,a_2) \text{ and } (a_2,a_1)$ (and similarly for the $b_i$).The number of inversions is therefore $$\binom{p}{2}\binom{q}{2} = \frac{p-1}{2}\frac{q-1}{2} \,(\text{mod }2)$$

Equating the two values for $\text{sgn}(\varphi)$ gives us our result.

I would like to add another proof of the Zolotarev's lemma. Consider $a\in\mathbb{Z}_p^{\times}$ and permutation $\tau_a\colon x\mapsto ax$. Note that for any permutation $\pi\in S(\mathbb{Z}_p)$ we have (here, we represent $\mathbb{Z}_p$ as set $\{0,1,\ldots,p-1\}$) $$ \text{sgn}~\pi=(-1)^{\text{inv}~\pi}=\prod_{0\leq i<j\leq p-1}\frac{\pi(i)-\pi(j)}{i-j}, $$ where $\text{inv}~\pi$ is a number of inversions. Hence, $$ \text{sgn}~\tau_a=\prod_{0\leq i<j\leq p-1}\frac{\tau_a(i)-\tau_a(j)}{i-j}. $$ Now, note that $\tau_a(i)\equiv a\cdot i\pmod p$, so $$ \text{sgn}~\tau_a\equiv\prod_{0\leq i<j\leq p-1}a=a^{p(p-1)/2}\equiv a^{(p-1)/2}\pmod p $$ due to Fermat's Little Theorem. Finally, by Euler's criterion we have $\left(\dfrac{a}{p}\right)\equiv a^{\frac{p-1}{2}}\pmod p$. Thus, $$ \text{sgn}~\tau_a\equiv\left(\dfrac{a}{p}\right)\pmod p, $$ which reduces to (because $\text{sgn}~\pi\in\{-1,1\}$ and $p>2$) $$ \text{sgn}~\tau_a=\left(\dfrac{a}{p}\right), $$ as desired.