Zolotarev's Lemma

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).