== 
In number theory, Zolotarev's lemma states that the Legendre symbol
for an integer a modulo a prime number p, can be computed as ε(πa) where ε denotes the signature of a permutation and πa the permutation of the residue classes mod p induced by modular multiplication by a, provided p does not divide a. Proof In general, for any finite group G of order n, it is easy to determine the signature of the permutation πg made by leftmultiplication by the element g of G. The permutation πg will be even, unless there are an odd number of orbits of even size. Assuming n even, therefore, the condition for πg to be an odd permutation, when g has order k, is that n/k should be odd, or that the subgroup <g> generated by g should have odd index. On the other hand, the condition to be an quadratic nonresidue is to be an odd power of a primitive root modulo p. The jth power of a primitive root, because the multiplicative group modulo p is a cyclic group, will by index calculus have index the greatest common divisor
The lemma therefore comes down to saying that i is odd when j is odd, which is true a fortiori, and j is odd when i is odd, which is true because p − 1 is even (unless p = 2 which is a trivial case). 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,...,p1} 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 U: x\mapsto ax (mod p):
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 iff 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. History This lemma was introduced by Yegor Ivanovich Zolotarev in an 1872 proof of quadratic reciprocity. See also: Gauss's lemma. References * Zolotareff G. (1872). "Nouvelle démonstration de la loi de de réciprocité de Legendre". Nouvelles Annales de Mathématiques, 2e série 11: 354—362. http://www.math.us.edu.pl/~szyjewski/Archiwum/Zolotarew/zolot01.pdf. Retrieved from "http://en.wikipedia.org/"

