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:
“The fact that several men were able to become infatuated with that latrine is truly the proof of the decline of the men of this century.”
—Charles Baudelaire (1821–1867)
“The source of Pyrrhonism comes from failing to distinguish between a demonstration, a proof and a probability. A demonstration supposes that the contradictory idea is impossible; a proof of fact is where all the reasons lead to belief, without there being any pretext for doubt; a probability is where the reasons for belief are stronger than those for doubting.”
—Andrew Michael Ramsay (1686–1743)