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:
| 1 | 2 | 3 | 4 | 5 |
| 10 | 9 | 8 | 7 | 6 |
Apply the permutation :
| 3 | 6 | 9 | 1 | 4 |
| 8 | 5 | 2 | 10 | 7 |
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:
| 3 | 5 | 2 | 1 | 4 |
| 8 | 6 | 9 | 10 | 7 |
Finally, apply a permutation W which gets back the original matrix:
| 1 | 2 | 3 | 4 | 5 |
| 10 | 9 | 8 | 7 | 6 |
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.
Read more about this topic: Zolotarev's Lemma
Famous quotes containing the word proof:
“A short letter to a distant friend is, in my opinion, an insult like that of a slight bow or cursory salutation—a proof of unwillingness to do much, even where there is a necessity of doing something.”
—Samuel Johnson (1709–1784)
“If any doubt has arisen as to me, my country [Virginia] will have my political creed in the form of a “Declaration &c.” which I was lately directed to draw. This will give decisive proof that my own sentiment concurred with the vote they instructed us to give.”
—Thomas Jefferson (1743–1826)