Rząd w grupie multiplikatywnej

Ten artykuł należy dopracować:

od 2022-02 → poprawić błędy językowe lub stylistyczne (pomoc: powszechne błędy językowe),
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ść:

a^{k}\ \equiv \ 1{\pmod {n}}

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 $\operatorname {ord} _{n}(a)$ .

Przykład

Mamy następujące potęgi 4 modulo 7:

{\begin{array}{llll}4^{0}&=1&=0\times 7+1&\equiv 1{\pmod {7}}\\4^{1}&=4&=0\times 7+4&\equiv 4{\pmod {7}}\\4^{2}&=16&=2\times 7+2&\equiv 2{\pmod {7}}\\4^{3}&=64&=9\times 7+1&\equiv 1{\pmod {7}}\\4^{4}&=256&=36\times 7+4&\equiv 4{\pmod {7}}\\4^{5}&=1024&=146\times 7+2&\equiv 2{\pmod {7}}\\\end{array}}

\vdots

Najmniejszą dodatnią liczbą całkowitą k taką, że $4^{k}\equiv 1$ (mod 7) jest 3, czyli $\operatorname {ord} _{7}(4)=3$ .

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 a^s ≡ a^t (mod n). Jako, że a i n są względnie pierwsze, to a ma element odwrotny a⁻¹, możemy więc wymnożyć obie strony przez a^−t otrzymując a^s−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 Z_n; ma on $\varphi (n)$ elementów, gdzie φ jest funkcją φ Eulera (tocjent) i jest oznaczana przez U(n) lub U(Z_n).

Na mocy twierdzenia Lagrange’a ord_n(a) jest dzielnikiem $\varphi (n)$ ^[1]. Jeśli $\operatorname {ord} _{n}(a)$ jest równy $\varphi (n)$ , 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 $\operatorname {ord} _{n}(a)$ .

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

Ten artykuł od 2022-02 zawiera treści, przy których brakuje odnośników do źródeł.

Należy dodać przypisy do treści niemających odnośników do źródeł. Dodanie listy źródeł bibliograficznych jest problematyczne, ponieważ nie wiadomo, które treści one uźródławiają.
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 2³², 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=p₀p₁...p_n, następnie, posługując się tablicą binarną, wykreślamy wielokrotności p_i 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.