Zolotarev's Lemma
   HOME

TheInfoList



OR:

In
number theory Number theory is a branch of pure mathematics devoted primarily to the study of the integers and arithmetic functions. Number theorists study prime numbers as well as the properties of mathematical objects constructed from integers (for example ...
, Zolotarev's lemma states that the
Legendre symbol In number theory, the Legendre symbol is a multiplicative function with values 1, −1, 0 that is a quadratic character modulo of an odd prime number ''p'': its value at a (nonzero) quadratic residue mod ''p'' is 1 and at a non-quadratic re ...
:\left(\frac\right) for an integer ''a''
modulo In computing and mathematics, the modulo operation returns the remainder or signed remainder of a division, after one number is divided by another, the latter being called the '' modulus'' of the operation. Given two positive numbers and , mo ...
an odd
prime number A prime number (or a prime) is a natural number greater than 1 that is not a Product (mathematics), product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime ...
''p'', where ''p'' does not divide ''a'', can be computed as the sign of a permutation: :\left(\frac\right) = \varepsilon(\pi_a) where ε denotes the
signature of a permutation In mathematics, when ''X'' is a finite set with at least two elements, the permutations of ''X'' (i.e. the bijective functions from ''X'' to ''X'') fall into two classes of equal size: the even permutations and the odd permutations. If any total ...
and π''a'' is the
permutation In mathematics, a permutation of a set can mean one of two different things: * an arrangement of its members in a sequence or linear order, or * the act or process of changing the linear order of an ordered set. An example of the first mean ...
of the nonzero
residue class In mathematics, modular arithmetic is a system of arithmetic operations for integers, other than the usual ones from elementary arithmetic, where numbers "wrap around" when reaching a certain value, called the modulus. The modern approach to mod ...
es mod ''p'' induced by
multiplication Multiplication is one of the four elementary mathematical operations of arithmetic, with the other ones being addition, subtraction, and division (mathematics), division. The result of a multiplication operation is called a ''Product (mathem ...
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).


Proof

In general, for any
finite group In abstract algebra, a finite group is a group whose underlying set is finite. Finite groups often arise when considering symmetry of mathematical or physical objects, when those objects admit just a finite number of structure-preserving tra ...
''G'' of order ''n'', it is straightforward to determine the signature of the permutation π''g'' made by left-multiplication by the element ''g'' of ''G''. The permutation π''g'' will be even, unless there are an odd number of
orbits In celestial mechanics, an orbit (also known as orbital revolution) is the curved trajectory of an physical body, object such as the trajectory of a planet around a star, or of a natural satellite around a planet, or of an satellite, artificia ...
of even size. Assuming ''n'' even, therefore, the condition for π''g'' to be an odd permutation, when ''g'' has order ''k'', is that ''n''/''k'' should be odd, or that the subgroup <''g''> generated by ''g'' should have odd
index Index (: indexes or indices) may refer to: Arts, entertainment, and media Fictional entities * Index (''A Certain Magical Index''), a character in the light novel series ''A Certain Magical Index'' * The Index, an item on the Halo Array in the ...
. We will apply this to the group of nonzero numbers mod ''p'', which is a
cyclic group In abstract algebra, a cyclic group or monogenous group is a Group (mathematics), group, denoted C_n (also frequently \Z_n or Z_n, not to be confused with the commutative ring of P-adic number, -adic numbers), that is Generating set of a group, ge ...
of order ''p'' − 1. The ''j''th power of a primitive root modulo p will have index the
greatest common divisor In mathematics, the greatest common divisor (GCD), also known as greatest common factor (GCF), of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. For two integers , , the greatest co ...
:''i'' = (''j'', ''p'' − 1). The condition for a nonzero number mod ''p'' to be a quadratic non-residue is to be an odd power of a primitive root. The lemma therefore comes down to saying that ''i'' is odd when ''j'' is odd, which is true ''a fortiori'', and ''j'' is odd when ''i'' is odd, which is true because ''p'' − 1 is even (''p'' is odd).


Another proof

Zolotarev's lemma can be deduced easily from Gauss's lemma and ''vice versa''. The example :\left(\frac\right), i.e. the Legendre symbol (''a''/''p'') with ''a'' = 3 and ''p'' = 11, will illustrate how the proof goes. Start with the set arranged as a matrix of two rows such that the sum of the two elements in any column is zero mod ''p'', say: Apply the permutation U: x\mapsto ax\pmod p: The columns still have the property that the sum of two elements in one column is zero mod ''p''. Now apply a permutation ''V'' which swaps any pairs in which the upper member was originally a lower member: Finally, apply a permutation W which gets back the original matrix: We have ''W''−1 = ''VU''. Zolotarev's lemma says (''a''/''p'') = 1 if and only if the permutation ''U'' is even. Gauss's lemma says (''a/p'') = 1 iff ''V'' is even. But ''W'' is even, so the two lemmas are equivalent for the given (but arbitrary) ''a'' and ''p''.


Jacobi symbol

This interpretation of the Legendre symbol as the sign of a permutation can be extended to the
Jacobi symbol Jacobi symbol for various ''k'' (along top) and ''n'' (along left side). Only are shown, since due to rule (2) below any other ''k'' can be reduced modulo ''n''. Quadratic residues are highlighted in yellow — note that no entry with a ...
:\left(\frac\right), where ''a'' and ''n'' are relatively prime integers with odd ''n'' > 0: ''a'' is invertible mod ''n'', so multiplication by ''a'' on Z/''n''Z 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.


History

This lemma was introduced by
Yegor Ivanovich Zolotarev Yegor (Egor) Ivanovich Zolotaryov () (31 March 1847, Saint Petersburg – 19 July 1878, Saint Petersburg) was a Russian mathematician. Biography Yegor was born as a son of Agafya Izotovna Zolotaryova and the merchant Ivan Vasilevich Zolotary ...
in an 1872 proof of
quadratic reciprocity In number theory, the law of quadratic reciprocity is a theorem about modular arithmetic that gives conditions for the solvability of quadratic equations modulo prime numbers. Due to its subtlety, it has many formulations, but the most standard st ...
.


References

*{{cite journal , author=Zolotareff G. , title=Nouvelle démonstration de la loi de réciprocité de Legendre , journal=
Nouvelles Annales de Mathématiques The ''Nouvelles Annales de Mathématiques'' (subtitled ''Journal des candidats aux écoles polytechnique et normale'') was a French scientific journal in mathematics. It was established in 1842 by Olry Terquem and Camille-Christophe Gerono, and c ...
, series= 2e série , volume=11 , year=1872 , pages=354–362 , url=http://archive.numdam.org/ARCHIVE/NAM/NAM_1872_2_11_/NAM_1872_2_11__354_0/NAM_1872_2_11__354_0.pdf


External links


PlanetMath article
on Zolotarev's lemma; includes his proof of quadratic reciprocity Articles containing proofs Lemmas in number theory Permutations Quadratic residue Squares in number theory