Zolotarev's lemma
In number theory, Zolotarev's lemma states that the Legendre symbol ( a p ) {\displaystyle \left({\frac {a}{p}}\right)} 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: ( a p ) = ε ( π a ) {\displaystyle \left({\frac {a}{p}}\right)=\varepsilon (\pi _{a})} 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.