Rząd w grupie multiplikatywnej
Sekcja własności, akapity od drugiego w dół i cztery ostatnie sekcje - poprawić język i styl.
Po wyeliminowaniu niedoskonałości należy usunąć szablon {{Dopracować}} z tego artykułu.
W teorii liczb, rzędem w grupie multiplikatywnej modulo n nazywamy najmniejszą liczbę całkowitą dodatnią k taką, że dla ustalonych, względnie pierwszych liczb a, n (a jest całkowite, n całkowite dodatnie) spełniona jest następująca zależność:
Innymi słowami, rząd a w grupie multiplikatywnej modulo n to rząd a jako elementu grupy multiplikatywnej w pierścieniu liczb całkowitych modulo n.
Rząd a modulo n jest zwykle oznaczany .
Przykład
Mamy następujące potęgi 4 modulo 7:
Najmniejszą dodatnią liczbą całkowitą k taką, że (mod 7) jest 3, czyli .
Własności
Nawet bez wiedzy, że działamy w grupie multiplikatywnej modulo n, możemy pokazać, że a faktycznie ma rząd, przez zauważenie, że potęgi a przybierać mogą jedynie skończoną liczbę różnych wartości modulo n. Zatem zgodnie z zasadą szufladkową Dirichleta muszą istnieć dwie potęgi: s i t. Bez straty ogólności można założyć, że s>t, takie że as ≡ at (mod n). Jako, że a i n są względnie pierwsze, to a ma element odwrotny a−1, możemy więc wymnożyć obie strony przez a−t otrzymując as−t≡1(mod n).
Idea rzędu modulo jest szczególnym przypadkiem rzędu elementu grupy. Rząd liczby a modulo n jest rzędem a w grupie multiplikatywnej modulo n, której elementy są resztami modulo n liczb względnie pierwszych z n, której operacją grupy jest mnożenie modulo n. To jest grupa elementów odwracalnych pierścienia Zn; ma on elementów, gdzie φ jest funkcją φ Eulera (tocjent) i jest oznaczana przez U(n) lub U(Zn).
Na mocy twierdzenia Lagrange’a ordn(a) jest dzielnikiem [1]. Jeśli jest równy , to a jest nazywane pierwiastkiem pierwotnym modulo n. Oznacza to, że grupa U(n) jest cykliczna i klasy reszt a generują ją.
Silniejszym twierdzeniem jest podzielność funkcji Carmicheala λ(n) przez rząd w grupie multiplikatywnej .
Rzędy na przykładach
Dla liczby pierwszej n=7, badamy kolejne liczby od 0 do 6 i ich potęgi, zaczynając od pierwszej, a kończąc, gdy cykl zacznie się powtarzać:
- 0) 0 // 0 nie względnie pierwsze z 7
- 1) 1 // rząd 1
- 2) 2 4 1 // rząd 3
- 3) 3 2 6 4 5 1 // rząd 6
- 4) 4 2 1 // rząd 3
- 5) 5 4 6 2 3 1 // rząd 6
- 6) 6 1 // rząd 2
Jedynie zero pozostaje zerem, a pozostałe ciągi kończą się na 1 i cykl rozpoczyna się od nowa.
Dla n=9, nie będącego liczbą pierwszą, mamy dwa rodzaje ciągów:
- 0) 0 // 0 nie względnie pierwsze z 9
- 1) 1 // rząd 1
- 2) 2 4 8 7 5 1 // rząd 6
- 3) 3 0 // 3 nie względnie pierwsze z 9
- 4) 4 7 1 // rząd 3
- 5) 5 7 8 4 2 1 // rząd 6
- 6) 6 0 // 6 nie względnie pierwsze z 9
- 7) 7 4 1 // rząd 3
- 8) 8 1 // rząd 2
Ciągi zaczynające się od 3 i 6 kończą się na zerze.
Pierwiastki pierwotne
Pierwiastek pierwotny (prymitywny), to taki element, którego rząd jest równy rzędowi grupy. W języku teorii grup, jest to element będący generatorem grupy. Potęgując pierwiastek pierwotny wygenerujemy całą grupę multiplikatywną.
Przykłady:
- Dla n = 7 mamy dwa pierwiastki: a = 3 i a = 5.
- Dla n = 9 pierwiastkami są a = 2 i a = 5.
- n = 8 nie posiada pierwiastków prymitywnych.
Jeżeli grupa modulo n posiada pierwiastek pierwotny, to liczba wszystkich pierwiastków pierwotnych wynosi φ(φ(n)).
Wysoki rząd
Sprawdź w źródłach: Encyklopedia PWN • Google Books • Google Scholar • Federacja Bibliotek Cyfrowych • BazHum • BazTech • RCIN • Internet Archive (texts / inlibrary)
Po wyeliminowaniu niedoskonałości należy usunąć szablon {{Dopracować}} z tego artykułu.
W grupach, zwłaszcza tych, dla których n jest duże, np. rzędu 232, jak w generatorze liczb pseudolosowych Lehmera, mówi się o rzędzie w grupie, który jest wysoki, choć a nie jest pierwiastkiem pierwotnym. Określenie rzędu jako wysokiego nie jest ściśle zdefiniowane, lecz jest to szacunkowe określenie. Weźmy grupę modulo 81, ma wiele pierwiastków pierwotnych o rzędach równych 54. Inne liczby względnie pierwsze z 81, a więc nie wielokrotności 9, dają rząd długości 27, jak 4:
- 4): 4 16 64 13 52 46 22 7 28 31 43 10 40 79 73 49 34 55 58 70 37 67 25 19 76 61 1 // rząd 27
a czasem tylko 9 czy tylko 3:
- 10): 10 19 28 37 46 55 64 73 1 // rząd 9
- 28): 28 55 1 // rząd 3
A więc dla tej grupy możemy powiedzieć, że 4 ma wysoki rząd.
Przykład kodu
Najpierw należy rozróżnić elementy, które są względnie pierwsze z n od tych, które nie są. Liczbę n rozkładamy na liczby pierwsze: n=p0p1...pn, następnie, posługując się tablicą binarną, wykreślamy wielokrotności pi dla każdego i. Dla n bierzemy liczby od 0 do n-1 i każdą podnosimy do kolejnych potęg modulo, aż wejdzie w cykl. Pierwiastek pierwotny mamy wtedy, gdy cykl wykorzysta wszystkie liczby będące względnie pierwsze z n.
- zobacz program prezentujący rząd w grupie multiplikatywnej
Zobacz też
- arytmetyka modularna
- logarytm dyskretny
- rząd (teoria grup)