- Zolotarev's lemma
In
mathematics , Zolotarev's lemma innumber theory states that theLegendre symbol :left(frac{a}{p} ight)
for an integer "a" "modulo" a
prime number "p", can be computed as:ε(π"a")
where ε denotes the
signature of a permutation and π"a" thepermutation of theresidue class es mod "p" induced bymodular 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 left-multiplication 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 non-residue is to be an odd power of aprimitive root modulo p . The "j"th power of a primitive root, because the multiplicative group modulo "p" is acyclic group , will byindex calculus have index thehcf :"i" = ("j", "p" − 1).
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:left(frac{3}{11} ight),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: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 ofquadratic reciprocity .See also: Gauss's lemma.
References
*E. Zolotarev, "Nouvelle démonstration de la loi de réciprocité de Legendre", Nouv. Ann. Math (2), 11 (1872), 354-362
External links
* [http://planetmath.org/?op=getobj&from=objects&id=4043 PlanetMath article] on Zolotarev's lemma; includes his proof of quadratic reciprocity
Wikimedia Foundation. 2010.