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.
Read more about this topic: Zolotarev's Lemma
Famous quotes containing the words jacobi and/or symbol:
“... spinsterhood [is considered to be] an abnormality of small proportions and small consequence, something like an extra finger or two on the body, presumably of temporary duration, and never of any social significance.”
—Mary Putnam Jacobi (1842–1906)
“A pool is, for many of us in the West, a symbol not of affluence but of order, of control over the uncontrollable. A pool is water, made available and useful, and is, as such, infinitely soothing to the western eye.”
—Joan Didion (b. 1934)