Zolotarev's Lemma - Another Proof

Another Proof

Zolotarev's lemma can be deduced easily from Gauss's lemma and vice versa. The example

,

i.e. the Legendre symbol (a/p) with a = 3 and p = 11, will illustrate how the proof goes. Start with the set {1, 2, . . ., p − 1} arranged as a matrix of two rows such that the sum of the two elements in any column is zero mod p, say:

Apply the permutation :

The columns still have the property that the sum of two elements in one column is zero mod p. Now apply a permutation V which swaps any pairs in which the upper member was originally a lower member:

Finally, apply a permutation W which gets back the original matrix:

We have W−1 = VU. Zolotarev's lemma says (a/p) = 1 if and only if the permutation U is even. Gauss's lemma says (a/p) = 1 iff V is even. But W is even, so the two lemmas are equivalent for the given (but arbitrary) a and p.