Zolotarev's Lemma - Jacobi Symbol

Jacobi Symbol

This interpretation of the Legendre symbol as the sign of a permutation can be extended to the Jacobi symbol

where a and n are relatively prime odd integers with n > 0: a is invertible mod n, so multiplication by a on Z/nZ is a permutation and a generalization of Zolotarev's lemma is that the Jacobi symbol above is the sign of this permutation.

For example, multiplication by 2 on Z/21Z has cycle decomposition (0)(1,2,4,8,16,11)(3,6,12)(5,10,20,19,17,13 (7,14)(9,18,15), so the sign of this permutation is (1)(−1)(1)(−1)(−1)(1) = −1 and the Jacobi symbol (2|21) is −1. (Note that multiplication by 2 on the units mod 21 is a product of two 6-cycles, so its sign is 1. Thus it's important to use all integers mod n and not just the units mod n to define the right permutation.)

When n = p is an odd prime and a is not divisible by p, multiplication by a fixes 0 mod p, so the sign of multiplication by a on all numbers mod p and on the units mod p have the same sign. But for composite n that is not the case, as we see in the example above.