Zolotarevovo lemma - Zolotarevs lemma - Wikipedia

v teorie čísel, Zolotarevovo lemma uvádí, že Legendární symbol

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

pro celé číslo A modulo zvláštní prvočíslo p, kde p nedělí A, lze vypočítat jako znak permutace:

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

kde ε označuje podpis permutace a π_A je permutace nenulové hodnoty zbytkové třídy mod p vyvolané násobení podle A.

Například vezměte A = 2 a p = 7. Nenulové čtverce mod 7 jsou 1, 2 a 4, takže (2 | 7) = 1 a (6 | 7) = -1. Násobení 2 na nenulová čísla mod 7 má rozklad cyklu (1,2,4) (3,6,5), takže znaménko této permutace je 1, což je (2 | 7). Násobení 6 na nenulová čísla mod 7 má cyklický rozklad (1,6) (2,5) (3,4), jehož znaménko je -1, což je (6 | 7).

Důkaz

Obecně platí, že pro všechny konečná skupina G řádu n, je jednoduché určit podpis permutace π_G provedeno násobením vlevo prvkem G z G. Permutace π_G bude sudé, pokud nebude lichý počet oběžné dráhy sudé velikosti. Za předpokladu n dokonce i podmínka pro π_G být lichá permutace, když G má pořádek k, je to n/k by měl být lichý, nebo že podskupina <G> generováno uživatelem G by měl mít zvláštní index.

Aplikujeme to na skupinu nenulových čísel mod p, což je cyklická skupina řádu p - 1. The jta síla a primitivní root modulo str bude indexový počet mít index největší společný dělitel

i = (j, p − 1).

Podmínka pro nenulové číslo mod p být a kvadratické nezbytky má být zvláštní silou primitivního kořene. Lemma tedy přichází k tomu, že to říká i je zvláštní, když j je liché, což je pravda tím spíše, a j je zvláštní, když i je liché, což je pravda, protože p - 1 je sudý (p je liché).

Další důkaz

Zolotarevovo lemma lze snadno odvodit z Gaussovo lema a naopak. Příklad

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

tj. symbol Legendre (A/p) s A = 3 a p = 11, bude ilustrovat, jak probíhá důkaz. Začněte sadou {1, 2,. . . ,p - 1} uspořádané jako matice dvou řádků tak, že součet dvou prvků v libovolném sloupci je nulový modp, řekněme:

Použijte permutaci ${ displaystyle U: x mapsto sekera { pmod {p}}}$:

Sloupce stále mají vlastnost, že součet dvou prvků v jednom sloupci je nulový mod p. Nyní použijte permutaci PROTI který zamění všechny páry, ve kterých byl horní člen původně spodním členem:

Nakonec použijte permutaci W, která získá zpět původní matici:

My máme Ž⁻¹ = VU. Zolotarevovo lemma říká (A/p) = 1 pouze a jen v případě permutace U je sudý. Gaussovo lemma říká (a / str) = 1 iff PROTI je sudý. Ale Ž is even, so the two lemmas are equivalent for the given (but arbitrary) A ap.

Jacobi symbol

Tuto interpretaci symbolu Legendre jako znaku permutace lze rozšířit na Jacobi symbol

${ displaystyle left ({ frac {a} {n}} right),}$

kde A a n jsou relativně primární lichá celá čísla s n > 0: A je invertible mod n, tedy násobení A na Z/nZ je permutace a zobecnění Zolotarevova lematu spočívá v tom, že výše uvedený symbol Jacobi je znamením této permutace.

Například násobení 2 na Z/21Z má rozklad cyklu (0) (1,2,4,8,16,11) (3,6,12) (5,10,20,19,17,13) (7,14) (9,18,15 ), takže znaménko této permutace je (1) (- 1) (1) (- 1) (- 1) (1) = −1 a symbol Jacobiho (2 | 21) je −1. (Všimněte si, že násobení 2 na jednotkách mod 21 je produktem dvou 6 cyklů, takže jeho znaménko je 1. Proto je důležité použít Všechno celá čísla mod n a nejen jednotky mod n definovat správnou permutaci.)

Když n = p je liché prvočíslo a A není dělitelné p, násobení A opravy 0 mod p, tedy znak násobení A na všech číslech mod p a na jednotkách mod p mít stejné znamení. Ale pro kompozitní n to není tento případ, jak vidíme ve výše uvedeném příkladu.

Dějiny

Toto lemma zavedlo Jegor Ivanovič Zolotarev v 1872 důkazu kvadratická vzájemnost.

Reference

• Zolotareff G. (1872). „Nouvelle démonstration de la loi de réciprocité de Legendre“ (PDF). Nouvelles Annales de Mathématiques. 2e série. 11: 354–362.

externí odkazy

• Článek PlanetMath na Zolotarevově lematu; zahrnuje jeho důkaz kvadratické vzájemnosti