Zolotarev's lemma

Ties Legendre symbols to permutation signatures
In number theory, Zolotarev's lemma states that the Legendre symbol

for an integer a modulo an odd prime number p, where p does not divide a, can be computed as the sign of a permutation:

where ε denotes the signature of a permutation and πa is the permutation of the nonzero residue classes mod p induced by multiplication by a. For example, take a = 2 and p = 7. The nonzero squares mod 7 are 1, 2, and 4, so (2|7) = 1 and (6|7) = −1. Multiplication by 2 on the nonzero numbers mod 7 has the cycle decomposition (1,2,4)(3,6,5), so the sign of this permutation is 1, which is (2|7). Multiplication by 6 on the nonzero numbers mod 7 has cycle decomposition (1,6)(2,5)(3,4), whose sign is −1, which is (6|7).

In general, for any finite group G of order n, it is straightforward 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. We will apply this to the group of nonzero numbers mod p, which is a cyclic group of order p − 1. The jth power of a primitive root modulo p will have index the greatest common divisor

i = (j, p − 1). The condition for a nonzero number mod p to be a quadratic non residue is to be an odd power of a primitive root. 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 (p is odd).

This lemma was introduced by Yegor Ivanovich Zolotarev in an 1872 proof of quadratic reciprocity.