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:
“It comes to pass oft that a terrible oath, with a swaggering accent sharply twanged off, gives manhood more approbation than ever proof itself would have earned him.”
—William Shakespeare (1564–1616)
“Sculpture and painting are very justly called liberal arts; a lively and strong imagination, together with a just observation, being absolutely necessary to excel in either; which, in my opinion, is by no means the case of music, though called a liberal art, and now in Italy placed even above the other two—a proof of the decline of that country.”
—Philip Dormer Stanhope, 4th Earl Chesterfield (1694–1773)