Rząd w grupie multiplikatywnej

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)$. 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

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.

• zobacz program prezentujący rząd w grupie multiplikatywnej

Zobacz też

• arytmetyka modularna
• logarytm dyskretny
• rząd (teoria grup)