There are only a handful of resources that discuss the Zolotarev proof of the quadratic reciprocity law. Let $n \in \mathbb{Z}$, $a \in \mathbb{Z}/n\mathbb{Z}$, and $(a, n) = 1$. We can define a permutation
$$ T: x \mapsto ax \pmod n. $$
The Zolotarev symbol
$$ \left( \frac{a}{n} \right) $$
is defined to be the sign of the permutation $T$. Why is this the same as the Legendre symbol?
I tried to prove this by dividing the work into two cases:
- If $a = b^2 \pmod n$, then the map $T_b: x \mapsto bx \pmod n$ has an even number of cycles.
- If $a \neq x^2 \pmod n$, then the permutation $T_a$ must have an odd number of cycles of even length.
I am not sure that last assertion is true. It is mostly just wishful thinking.
Zolotarev's lemma seems to have been left as an exercise in Conway's book on Quadratic Forms. There are other resources which take a less whimsical route: