Zolotarev\'s lemma - Citizendia

In mathematics, Zolotarev's lemma in number theory states that the Legendre symbol

$\left(\frac{a}{p}\right)$

for an integer a modulo a prime number p, can be computed as

ε(π_a)

where ε denotes the signature of a permutation and π_a the permutation of the residue classes mod p induced by modular multiplication by a, provided p does not divide a. Mathematics is the body of Knowledge and Academic discipline that studies such concepts as Quantity, Structure, Space and Number theory is the branch of Pure mathematics concerned with the properties of Numbers in general and Integers in particular as well as the wider classes The Legendre symbol or quadratic character is a function introduced by Adrien-Marie Legendre in 1798 during his partly successful attempt to prove the Law of In Mathematics, modular arithmetic (sometimes called modulo arithmetic, or clock arithmetic) is a system of Arithmetic for Integers In Mathematics, a prime number (or a prime) is a Natural number which has exactly two distinct natural number Divisors 1 In Mathematics, the Permutations of a Finite set (ie the bijective mappings from the set to itself fall into two classes of equal size the even In several fields of Mathematics the term permutation is used with different but closely related meanings In Mathematics, modular arithmetic (sometimes called modulo arithmetic, or clock arithmetic) is a system of Arithmetic for Integers In Mathematics, modular arithmetic (sometimes called modulo arithmetic, or clock arithmetic) is a system of Arithmetic for Integers

1 Proof
2 Another proof
3 History
4 References
5 External links

Proof

In general, for any finite group G of order n, it is easy to determine the signature of the permutation π_g made by left-multiplication by the element g of G. In Mathematics, a finite group is a group which has finitely many elements The permutation π_g will be even, unless there are an odd number of orbits of even size. In Algebra and Geometry, a group action is a way of describing symmetries of objects using groups. 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.

On the other hand, the condition to be an quadratic non-residue is to be an odd power of a primitive root modulo p. An Integer q is called a quadratic residue modulo n if it is congruent to a perfect square (mod n) i In Modular arithmetic, a branch of Number theory, a primitive root modulo n is any number g with the property that any number Coprime The jth power of a primitive root, because the multiplicative group modulo p is a cyclic group, will by index calculus have index the hcf

i = (j, p − 1). In Group theory, a cyclic group or monogenous group is a group that can be generated by a single element in the sense that the group has an In Group theory, the index calculus algorithm is an Algorithm for computing Discrete logarithms This is the best known algorithm for certain groups such

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 (unless p = 2 which is a trivial case).

Another proof

Zolotarev's lemma can be deduced easily from Gauss's lemma and vice versa. Gauss's lemma can mean any of several lemmas named after Carl Friedrich Gauss: Gauss's lemma (polynomial Gauss's lemma The example

$\left(\frac{3}{11}\right)$ ,

i. e. the Legendre symbol (a/p) with a=3 and p=11, will illustrate how the proof goes. Start with the set {1,2,. . . ,p-1} arranged as a matrix of two rows such that the sum of the two elements in any column is zero mod p, say:

1	2	3	4	5
10	9	8	7	6

Apply the permutation $U: x\mapsto ax$ (mod $p$ ):

3	6	9	1	4
8	5	2	10	7

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:

3	5	2	1	4
8	6	9	10	7

Finally, apply a permutation W which gets back the original matrix:

1	2	3	4	5
10	9	8	7	6

We have W ^-1=VU. Zolotarev's lemma says (a/p)=1 iff 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.

History

This lemma was introduced by Yegor Ivanovich Zolotarev in an 1872 proof of quadratic reciprocity. Yegor (Egor Ivanovich Zolotarev (Егор Иванович Золотарёв ( March 31, 1847 – July 19, 1878) was a Russian The law of quadratic reciprocity is a theorem from Modular arithmetic, a branch of Number theory, which shows a remarkable relationship between the solvability

See also: Gauss's lemma. This article is about Gauss's lemma in number theory Gauss's lemma (polynomial concerns factoring polynomials

References

E. Zolotarev, Nouvelle démonstration de la loi de réciprocité de Legendre, Nouv. Ann. Math (2), 11 (1872), 354-362

External links

PlanetMath article on Zolotarev's lemma; includes his proof of quadratic reciprocity

© 2009 citizendia.org; parts available under the terms of GNU Free Documentation License, from http://en.wikipedia.org
network: | |

Contents

Proof

Another proof

History

References

External links