Prove that the Zolotarev symbol is the same as Legendre and Jacobi symbols

Question

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:

• [1] Proofs of QR

• [2] Wikipedia

• [3] Nouvelle démonstration de la loi de réciprocité de Legendre (Zolotareff)

Answer 1

The proof that the Zolotarev symbol is the same as the Legendre symbol is given at Wikipedia and also in another document as Lemma 1.

The proof that the Zolotarev symbol is the same as the Jacobi symbol is given in five pages in that same document.