Elementy Pierwotne (prymitywne)

[dawidcc]

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!

[karolex123]

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 \(\displaystyle{ n}\), to to z definicji generator grupy multiplikatywnej \(\displaystyle{ \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 \(\displaystyle{ \varphi(n)}\).
Dowodzi się, że grupa multiplikatywna \(\displaystyle{ \mathbb{Z}_p ^{*}}\) jest cykliczna, tj. istnieje element pierwotny (\(\displaystyle{ p}\) jest liczbą pierwszą). Jednak dowód jest zupełnie niekonstruktywny, a znalezienie pierwiastka pierwotnego modulo \(\displaystyle{ p}\) jest często bardzo trudne.

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

[karolex123]

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

[Gosda]

Nie trzeba sprawdzać wszystkich elementów, zresztą dla większych grup to się zaczyna robić czasochłonne. Na

Kod: Zaznacz cały

https://en.wikipedia.org/wiki/Primitive_root_modulo_n#Finding_primitive_roots

jest podany lepszy algorytm.

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

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

[karolex123]

Niestety to co napisałeś nie działa. weźmy na przykład \(\displaystyle{ 9}\). Wtedy \(\displaystyle{ 9^2=81=19}\), \(\displaystyle{ 9^3=171=16}\) i \(\displaystyle{ 9^5=25}\) (oczywiście wszystkie równości modulo \(\displaystyle{ 31}\)), a \(\displaystyle{ 9}\) nie jest pierwiastkiem pierwotnym modulo \(\displaystyle{ 9}\) (dokładniej, ma rząd \(\displaystyle{ 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 \(\displaystyle{ \mathbb{Z} / 31 \mathbb{Z}}\) oznacza prędzej grupę (albo częściej pierścień ilorazowy) liczb całkowitych modulo \(\displaystyle{ 31}\) z dodawaniem, a nie grupę liczb względnie pierwszych z \(\displaystyle{ 31}\) modulo \(\displaystyle{ 31}\) z mnożeniem

[Gosda]

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

[karolex123]

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

[dawidcc]

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?

[karolex123]

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 \(\displaystyle{ \mathbb{Z}_n^*}\) jest \(\displaystyle{ \varphi(n)}\), zatem każdy element ma rząd będący dzielnikiem liczby \(\displaystyle{ \varphi(n)}\). Teraz, załóżmy, że element \(\displaystyle{ a \in \mathbb{Z}_n^*}\) nie jest pierwotny, niech \(\displaystyle{ r}\) oznacza jego rząd. Wtedy \(\displaystyle{ r | \varphi(n)}\). Istnieje jednak liczba pierwsza \(\displaystyle{ p}\) dzieląca \(\displaystyle{ \varphi(n)}\), która dzieli \(\displaystyle{ \displaystyle{\frac{\varphi(n)}{r}}}\) (bo \(\displaystyle{ r \neq \varphi(n)}\)). Ale to oznacza, że \(\displaystyle{ \displaystyle{r| \frac{\varphi(n)}{p}}}\), zatem \(\displaystyle{ \displaystyle{a^{\frac{\varphi(n)}{p}}=1}}\). To dowodzi faktu, że wystarcza sprawdzać wykładniki postaci \(\displaystyle{ \displaystyle{\frac{\varphi(n)}{p}}}\), gdzie \(\displaystyle{ p}\) przebiega dzielniki pierwsze \(\displaystyle{ \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 \(\displaystyle{ n}\), to jest ich wśród kandydatów dokładnie \(\displaystyle{ \varphi \big( \varphi(n) \big)}\). W przypadku grupy \(\displaystyle{ \mathbb{Z}_{31}^*}\) mamy więc \(\displaystyle{ \varphi(30)=2 \cdot 4=8}\) pierwiastków pierwotnych, co jest prawie trzecią częścią całej grupy

[dawidcc]

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