Rząd w grupie multiplikatywnej

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania

W teorii liczb dana liczba całkowita a i dodatnia liczba całkowita n z nwd(a,n) = 1 (czyli liczby a i n są to liczby względnie pierwsze), rzędem w grupie multiplikatywnej modulo n jest najmniejsza dodatnia liczba całkowita k taka że:

Innymi słowy, rząd a grupy multiplikatywnej modulo n jest to rząd a w grupie multiplikatywnej elementu odwracalnego w pierścieniu liczb całkowitych modulo n.

Rząd a modulo n jest zwykle zapisywany przez ordn(a) lub On(a).

Przykład[edytuj | edytuj kod]

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

Najmniejszą dodatnią liczbą całkowitą k taka że 4k = 1 (mod 7) jest 3, tak że ord7(4) = 3.

Aby otrzymać te same wyniki, możemy kolejno mnożyć przez 4 same reszty modulo 7:

1 * 4 mod 7 = 4
4 * 4 mod 7 = 2
2 * 4 mod 7 = 1
1 * 4 mod 7 = 4
4 * 4 mod 7 = 2
2 * 4 mod 7 = 1

Zauważmy, że po napotkaniu reszty jedynki cykl się powtarza.

Własności[edytuj | edytuj kod]

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 mogą jedynie przybierać skończoną liczbę różnych wartości modulo n, zgodnie więc z zasadą szufladkową Dirichleta muszą być dwie potęgi, powiedzmy s i t i bez straty ogólności s > t, takie że as ≡ at (mod n). Skoro a i nwzględnie pierwsze, to pociąga za sobą, że a ma odwrotny element a−1 i możemy wymnożyć obie strony przystawania przez at, otrzymując ast ≡ 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 in φ(n) elementów, gdzie φ jest funkcją φ Eulera (tocjent) i jest oznaczana przez U(n) or U(Zn).

Jako konsekwencja twierdzenia Lagrange’a ordn(a) jest dzielnikiem φ(n)[1]. Jeśli ordn a jest faktycznie równe φ(n) i dlatego tak duże jak to tylko możliwe, wtedy a jest nazywane pierwiastkiem pierwotnym modulo n. To oznacza, że grupa U(n) jest cykliczna i klasy reszt a generują ją.

Rząd ordn a również jest dzielnikiem λ(n), wartość funkcji Carmichaela, co jest nawet silniej stwierdzone niż podzielność of φ(n).

Rzędy na przykładach[edytuj | edytuj kod]

Dla n=7, które jest liczbą pierwszą, badamy kolejne liczby 0..6 i ich potęgi, zaczynając od pierwszej, a kończąc, gdy cykl grozi powtórzeniem:

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, które nie jest liczba pierwszą i się rozkłada na 3*3, 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

Zaczynające się od 3 i 6 kończą się na zerze.

Pierwiastki pierwotne[edytuj | edytuj kod]

Dla n=7 mamy dwa pierwiastki: a=3 i a=5, dla n=9 pierwiastkami są a=2 i a=5. Pierwiastki pierwotne to takie liczby mające w cyklu wszystkie liczby 0..n-1, które są względnie pierwsze. Tak więc dla n=7 są to wszystkie 6 liczb z wyjątkiem zera, a dla n=9 6 liczb z wyjątkiem zera, 3 i 6.

Wysoki rząd[edytuj | edytuj kod]

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 wysoki nie jest ściśle zdefiniowane, ale 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 27 ma wysoki rząd.

Przykład kodu[edytuj | edytuj kod]

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 = p0*p1*...*pn, następnie, posługując się tablicą binarną, wykreślamy wielokrotności pi dla każdego i. Dla n bierzemy liczy 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 też[edytuj | edytuj kod]

Przypisy[edytuj | edytuj kod]

  1. Rzędy Elementów Grupy Abelowej, Andrzej Nowicki 16 września 2015.