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:
“During the long ages of class rule, which are just beginning to cease, only one form of sovereignty has been assigned to all men—that, namely, over all women. Upon these feeble and inferior companions all men were permitted to avenge the indignities they suffered from so many men to whom they were forced to submit.”
—Mary Putnam Jacobi (1842–1906)
“In a symbol there is concealment and yet revelation: here therefore, by silence and by speech acting together, comes a double significance.... In the symbol proper, what we can call a symbol, there is ever, more or less distinctly and directly, some embodiment and revelation of the Infinite; the Infinite is made to blend itself with the Finite, to stand visible, and as it were, attainable there. By symbols, accordingly, is man guided and commanded, made happy, made wretched.”
—Thomas Carlyle (1795–1881)