1
$\begingroup$

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)

$\endgroup$
1
  • $\begingroup$ The Legendre symbol is only defined when the bottom number is an odd prime ... so do you mean to restrict $n$ to odd primes? In any event, the size of every cycle of $T$ is exactly the order of $a$ modulo $n$, so the number of cycles is $\phi(n)$ divided by this order. When $n$ is an odd prime, you can correlate whether this quotient is even/odd with whether $a$ is/isn't a quadratic residue, using the fact that a primitive root exists. $\endgroup$
    – Greg Martin
    Mar 5, 2017 at 20:58

1 Answer 1

Reset to default
1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .