Zolotarev's lemma

From Wikipedia, the free encyclopedia

In mathematics, Zolotarev's lemma in number theory states that the Legendre symbol

$\left(\frac{a}{p}\right)$

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.

1 Proof
2 History
3 Reference
4 External link

[edit] 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 jth 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).