Zolotarev's lemma

In mathematics, Zolotarev's lemma in number theory states that the Legendre 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" 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 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 a primitive root modulo p. The "j"th power of a primitive root, because the multiplicative group modulo "p" is a cyclic group, will by index calculus have index the hcf

:"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 of quadratic 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