Lemma Zolotarev

I talteorin anger Zolotarev Lemma att Legendre-symbolen

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

för ett heltal a modulo kan ett udda primtal p som inte delar a , beräknas som ett permutationstecken:

\left({\frac {a}{p}}\right)=\varepsilon (\pi _{a})

där ε betecknar tecknet för permutationen och π är permutationen av rester som inte är noll, mod p , erhållen genom att multiplicera med a .

Bevis från Gauss lemma

Zolotarev-lemmat härleds lätt från Gauss-lemmat och vice versa. Till exempel,

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

är Legendre-symbolen (a / p) för a = 3 och p = 11. Låt oss börja med mängden {1,2, ..., p-1} som en matris av två rader, så att summan av de två element i en kolumn är lika med noll modulo r , till exempel:

ett	2	3	fyra	5
tio	9	åtta	7	6

Låt oss tillämpa en permutation (mod p): $U:x\maps to ax$

3	6	9	ett	fyra
åtta	5	2	tio	7

Kolumner har också egenskapen att summan av två element i en kolumn är noll modulo p. Tillämpa nu ersättningen V , som kommer att byta två valfria par där den översta medlemmen ursprungligen var den nedre delen:

3	5	2	ett	fyra
åtta	6	9	tio	7

Slutligen tillämpar vi permutationen W, som kommer att returnera den ursprungliga matrisen tillbaka:

ett	2	3	fyra	5
tio	9	åtta	7	6

Alltså W −1 = VU. Zolotarev-lemmat anger att (a / p) = 1 om och endast om permutationen U är jämn. Gauss Lemma säger att (a / p) = 1 om och endast om V är jämnt. Men W är jämnt, så båda lemman är ekvivalenta för givet (men godtyckligt) a och p .

Allmänt fall

I allmänhet, låt vara någon ändlig grupp av jämn ordning . Låt vara ett ordningsmoment . Å ena sidan, om , då är inte en kvadrat i om och endast om , det vill säga är udda, utan är jämn. Å andra sidan, låt vara permutationen som genereras av elementet . Det är tydligt att det kan sönderdelas till en produkt av cykler av samma längd . Permutationsparitet . Det betyder att det är en udda permutation om och bara om den sönderfaller till ett udda antal cykler av jämn längd . Således är det även om och bara om det är en kvadrat. $G$ $n$ $a\i G$ $d$ $n=2^{r}q,2\nmid q$ $a$ $G$ $2^{r}\mid d$ ${\frac {n}{d))$ $d$ $\pi _{a}:g\mapsto ag$ $a$ $\pi _{a}$ ${\frac {|G|}{d))$ $d$ ${\displaystyle \varepsilon (\pi _{a})=(-1)^({\frac {|G|}{d}}(d-1)))$ $\pi _{a}$ $\pi _{a}$ ${\frac {|G|}{d))$ $d$ $\pi _{a}$ $a$

Satsen för Legendre-symbolen erhålls genom att ta gruppen av rester som inte är noll modulo . Ordningen för denna grupp är , och därför även för . $G$ ${\mathbb {Z}}_{p}^{{\times }}$ $sid$ $p-1$ $p>2$

Historik

Detta lemma användes av Egor Ivanovich Zolotarev 1872 i hans nya bevis på kvadratisk ömsesidighet .

Anteckningar

Zolotareff G. Nouvelle demonstration de la loi de de réciprocité de Legendre (franska) // Nouvelles Annales de Mathématiques :tidskrift. - 1872. - Vol. 11 . - s. 354-362 .

Länkar

En artikel om PlanetMath-resursen om Zolotarevs lemma; inkluderar hans bevis på kvadratisk ömsesidighet.