Elementy Pierwotne (prymitywne)

Grupy, pierścienie, ciała, rozkładalność, klasyczne struktury algebraiczne...
dawidcc
Użytkownik
Użytkownik
Posty: 4
Rejestracja: 12 maja 2019, o 19:10
Płeć: Mężczyzna
Lokalizacja: Polska

Elementy Pierwotne (prymitywne)

Post autor: dawidcc » 7 wrz 2019, o 13:18

Witam, staram się zrozumieć pojęcie elementów pierwotnych (prymitywnych). Rozumiem w jaki sposób wylicza się ich ilość, korzystając funkcji Eulera, jednak nie wiem czy dalsze postępowanie jest dla mnie jasne. Znajdujemy element taki, który po podniesieniu kolejno do większych potęg będzie spełniał naszą grupę? nie rozumiem tego elementu rozwinięcia ciała (przedstawienia w postaci zbioru).
Czy mógłby ktoś przedstawić mi to zjawisko na przykładzie np.
$$\mathbb{Z}^{∗}_{31}$$

Z góry dziękuję za pomoc!

Awatar użytkownika
karolex123
Użytkownik
Użytkownik
Posty: 721
Rejestracja: 22 gru 2012, o 11:01
Płeć: Mężczyzna
Lokalizacja: somewhere

Re: Elementy Pierwotne (prymitywne)

Post autor: karolex123 » 7 wrz 2019, o 17:00

Sformułowanie: "będzie spełniał naszą grupę" jest zupełnie niejasne i niefortunne. Poza tym to jest problem czysto algebraiczny
Element pierwotny modulo liczba całkowita \(n\), to to z definicji generator grupy multiplikatywnej \(\mathbb{Z}_n^{*}\), o ile istnieje. Oznacza to, że podnosząc taki element to kolejnych potęg, otrzymamy wszystkie elementy tej grupy. Innymi słowy, rząd elementu pierwotnego ma być równy rzędowi grupy, a więc \(\varphi(n)\).
Dowodzi się, że grupa multiplikatywna \(\mathbb{Z}_p ^{*}\) jest cykliczna, tj. istnieje element pierwotny (\(p\) jest liczbą pierwszą). Jednak dowód jest zupełnie niekonstruktywny, a znalezienie pierwiastka pierwotnego modulo \(p\) jest często bardzo trudne.

Weźmy np. grupę \(\mathbb{Z}_{31}^{*}\). Wiemy, że element pierwotny istnieje, więc pozostaje go tylko znaleźć. Ta grupa ma \(30\) elementów, więc jest trochę szukania

Awatar użytkownika
karolex123
Użytkownik
Użytkownik
Posty: 721
Rejestracja: 22 gru 2012, o 11:01
Płeć: Mężczyzna
Lokalizacja: somewhere

Re: Elementy Pierwotne (prymitywne)

Post autor: karolex123 » 7 wrz 2019, o 17:29

na moje oko jak sobie rozpisałem 3 powinno działać

Awatar użytkownika
Gosda
Użytkownik
Użytkownik
Posty: 75
Rejestracja: 29 cze 2019, o 19:46
Płeć: Mężczyzna
Lokalizacja: Oulu

Re: Elementy Pierwotne (prymitywne)

Post autor: Gosda » 7 wrz 2019, o 17:41

Nie trzeba sprawdzać wszystkich elementów, zresztą dla większych grup to się zaczyna robić czasochłonne. Na https://en.wikipedia.org/wiki/Primitive ... tive_roots jest podany lepszy algorytm.

Tutaj mamy \(n = 31\), dlatego rozkładamy \(\varphi(31) = 30 = 2 \cdot 3 \cdot 5\) i sprawdzamy dla kolejnych liczb, czy ich kwadrat, sześcian i piąta potęga modulo \(31\) są różne od \(1\). Dla \(m = 2\) mamy \(4, 8, 32 = 1\), czyli odpada. Dla \(m = 3\) mamy \(9, 27, 243 = 243 - 248 = -5 = 26\), czyli to jest generator grupy \(\mathbb Z/31\mathbb Z\).

Piszę \(\mathbb Z/31\mathbb Z\), bo standardowo \(\mathbb Z_p\) oznacza się liczby \(p\)-adyczne.

Awatar użytkownika
karolex123
Użytkownik
Użytkownik
Posty: 721
Rejestracja: 22 gru 2012, o 11:01
Płeć: Mężczyzna
Lokalizacja: somewhere

Re: Elementy Pierwotne (prymitywne)

Post autor: karolex123 » 7 wrz 2019, o 17:57

Niestety to co napisałeś nie działa. weźmy na przykład \(9\). Wtedy \(9^2=81=19\), \(9^3=171=16\) i \(9^5=25\) (oczywiście wszystkie równości modulo \(31\)), a \(9\) nie jest pierwiastkiem pierwotnym modulo \(9\) (dokładniej, ma rząd \(15\)). Algorytm który miałeś na myśli angażuje jednak nieco wyższe wykładniki :)

Nie zmienia to jednak faktu, że nie istnieje ogólna formuła szukania pierwiastka pierwotnego; konieczne jest sprawdzanie potencjalnie wszystkich i to właśnie miałem na myśli.

Zaś oznaczenie \(\mathbb{Z} / 31 \mathbb{Z}\) oznacza prędzej grupę (albo częściej pierścień ilorazowy) liczb całkowitych modulo \(31\) z dodawaniem, a nie grupę liczb względnie pierwszych z \(31\) modulo \(31\) z mnożeniem

Awatar użytkownika
Gosda
Użytkownik
Użytkownik
Posty: 75
Rejestracja: 29 cze 2019, o 19:46
Płeć: Mężczyzna
Lokalizacja: Oulu

Re: Elementy Pierwotne (prymitywne)

Post autor: Gosda » 7 wrz 2019, o 21:09

Racja: zamiast podnosić do potęg \(p_i\), trzeba to zrobić z \(\varphi(n) / p_i\), czyli w naszym przypadku: piętnasta, dziesiąta i szósta.

Awatar użytkownika
karolex123
Użytkownik
Użytkownik
Posty: 721
Rejestracja: 22 gru 2012, o 11:01
Płeć: Mężczyzna
Lokalizacja: somewhere

Re: Elementy Pierwotne (prymitywne)

Post autor: karolex123 » 8 wrz 2019, o 10:23

Tak. Dobrze jest także rozumieć, dlaczego to wystarcza

dawidcc
Użytkownik
Użytkownik
Posty: 4
Rejestracja: 12 maja 2019, o 19:10
Płeć: Mężczyzna
Lokalizacja: Polska

Re: Elementy Pierwotne (prymitywne)

Post autor: dawidcc » 10 wrz 2019, o 14:46

Dziękuję bardzo za odpowiedzi, już więcej rozumiem. Wcześniej sformułowanie "co spełnia daną grupę" nie wiedziałem jak inaczej nazwać. Teraz wiem, że badamy elementy, które są względnie pierwsze z ciałem (mam na myśli 31). Więc rozumiem już w jaki sposób to robić, tylko pozostają dwa pytania.
Nie wiem jak rozumieć ten moment kiedy podnosimy do potęg, ale nie $$p_{i}$$ tylko dzielimy funkcje Eulera przez te elementy? Skoro wychodzą wyniki 15, 10 i 6 to nie mogę znaleźć w tym konsekwencji dlaczego?
Drugie pytanie odnośnie sprawdzania po kolei potęg. Gdybym zdecydował się na taki sposób, to mam 30 liczb do sprawdzenia, więc musiałbym liczyć wszystkie 30 do wszystkich 30 potęg, czy można to w miarę oszacować na przykład do pierwszych 5-6?

Awatar użytkownika
karolex123
Użytkownik
Użytkownik
Posty: 721
Rejestracja: 22 gru 2012, o 11:01
Płeć: Mężczyzna
Lokalizacja: somewhere

Re: Elementy Pierwotne (prymitywne)

Post autor: karolex123 » 10 wrz 2019, o 22:02

Odpowiem na oba pytania. Trzeba sprawdzać. Wszystkie elementy. Chcemy to jednak robić nieco inteligentniej, niż podnosić każdy element do kolejnych trzydziestu potęg. Korzystam z podstawowej wiedzy na temat grup. Rząd elementu dzieli rząd grupy. Oczywiście rzędem grupy \(\mathbb{Z}_n^*\) jest \(\varphi(n)\), zatem każdy element ma rząd będący dzielnikiem liczby \(\varphi(n)\). Teraz, załóżmy, że element \(a \in \mathbb{Z}_n^*\) nie jest pierwotny, niech \(r\) oznacza jego rząd. Wtedy \(r | \varphi(n)\). Istnieje jednak liczba pierwsza \(p\) dzieląca \(\varphi(n)\), która dzieli \(\displaystyle{\frac{\varphi(n)}{r}}\) (bo \(r \neq \varphi(n)\)). Ale to oznacza, że \(\displaystyle{r| \frac{\varphi(n)}{p}}\), zatem \(\displaystyle{a^{\frac{\varphi(n)}{p}}=1}\). To dowodzi faktu, że wystarcza sprawdzać wykładniki postaci \(\displaystyle{\frac{\varphi(n)}{p}}\), gdzie \(p\) przebiega dzielniki pierwsze \(\varphi(n)\). Jest to fakt naprawdę prosty, naturalny i intuicyjny, ponadto korzysta z naprawdę elementarnej wiedzy. Nie przyspiesza on tak czy owak zbytnio procesu szukania elementu pierwotnego, bowiem wymaga podnoszenia to dosyć wysokich potęg i nadal trzeba sprawdzać z grubsza wszystkie elementy. Zauważmy jednak, że że jeżeli istnieje pierwiastek pierwotny modulo \(n\), to jest ich wśród kandydatów dokładnie \(\varphi \big( \varphi(n) \big)\). W przypadku grupy \(\mathbb{Z}_{31}^*\) mamy więc \(\varphi(30)=2 \cdot 4=8\) pierwiastków pierwotnych, co jest prawie trzecią częścią całej grupy :D

dawidcc
Użytkownik
Użytkownik
Posty: 4
Rejestracja: 12 maja 2019, o 19:10
Płeć: Mężczyzna
Lokalizacja: Polska

Re: Elementy Pierwotne (prymitywne)

Post autor: dawidcc » 11 wrz 2019, o 15:33

Jasne, już wszystko rozumiem. Dziękuję bardzo za odpowiedź!

ODPOWIEDZ