Rząd w grupie multiplikatywnej modulo n – w teorii liczb, najmniejsza dodatnia liczba całkowita , taka, że dla ustalonych liczb a, n, które są względnie pierwsze (przy czym a jest liczbą całkowitą, a n – dodatnią liczbą całkowitą), zachodzi:

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

Rząd modulo oznacza się zwykle:

.

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

Najmniejszą dodatnią liczbą całkowitą taką, że jest 3, czyli .

Własności Nawet bez odwoływania się do pojęcia grupy multiplikatywnej modulo n, można wykazać, że element faktycznie posiada rząd. Wynika to z faktu, że kolejne potęgi mogą przyjmować jedynie skończoną liczbę różnych wartości modulo .

Zatem, zgodnie z zasadą szufladkową Dirichleta, muszą istnieć dwie potęgi oraz (przy czym bez straty ogólności można założyć, że ), dla których zachodzi kongruencja:

.

Ponieważ oraz są względnie pierwsze, element posiada element odwrotny modulo . Można więc obustronnie wymnożyć powyższą kongruencję przez , uzyskując:

.

Pojęcie rzędu liczby modulo jest szczególnym przypadkiem rzędu elementu grupy. Rząd liczby modulo oznacza rząd jako elementu grupy multiplikatywnej modulo , czyli grupy złożonej z klas reszt modulo liczb względnie pierwszych z , w której działaniem jest mnożenie modulo .

Grupa ta stanowi zbiór elementów odwracalnych pierścienia i zawiera dokładnie elementów, gdzie oznacza funkcję Eulera (tocjent). Grupę tę oznacza się najczęściej jako , lub .

Na mocy twierdzenia Lagrange’a, rząd modulo , oznaczany jako , jest dzielnikiem . Jeśli , wówczas jest pierwiastkiem pierwotnym modulo . Oznacza to, że grupa jest cykliczna, a kolejne potęgi generują całą grupę.

Silniejszym twierdzeniem jest stwierdzenie, że rząd elementu w grupie multiplikatywnej modulo , czyli , jest dzielnikiem wartości funkcji Carmichaela .

Przykłady rzędu elementów Dla liczby pierwszej badamy rzędy kolejnych liczb całkowitych od 0 do 6. W każdym przypadku wyznaczamy kolejne potęgi danego elementu modulo 7, aż do uzyskania reszty 1, co oznacza zakończenie cyklu:

0 – brak rzędu; 0 nie jest względnie pierwsze z 7. 1 – rząd 1 (ciąg: 1). 2 – rząd 3 (ciąg: 2, 4, 1). 3 – rząd 6 (ciąg: 3, 2, 6, 4, 5, 1). 4 – rząd 3 (ciąg: 4, 2, 1). 5 – rząd 6 (ciąg: 5, 4, 6, 2, 3, 1). 6 – rząd 2 (ciąg: 6, 1).

W przypadku , które nie jest liczbą pierwszą, sytuacja wygląda następująco:

0 – brak rzędu; 0 nie jest względnie pierwsze z 9. 1 – rząd 1 (ciąg: 1). 2 – rząd 6 (ciąg: 2, 4, 8, 7, 5, 1). 3 – brak rzędu; 3 nie jest względnie pierwsze z 9 (ciąg kończy się zerem). 4 – rząd 3 (ciąg: 4, 7, 1). 5 – rząd 6 (ciąg: 5, 7, 8, 4, 2, 1). 6 – brak rzędu; 6 nie jest względnie pierwsze z 9 (ciąg kończy się zerem). 7 – rząd 3 (ciąg: 7, 4, 1). 8 – rząd 2 (ciąg: 8, 1).

Elementy, które nie są względnie pierwsze z 9 (takie jak 3 i 6), nie posiadają rzędu, ponieważ nie należą do grupy multiplikatywnej modulo 9 – ich potęgi prowadzą do zera.

W obu przypadkach potęgi elementów, które są względnie pierwsze z , tworzą cykle kończące się resztą 1.

Pierwiastki pierwotne Pierwiastek pierwotny (nazywany także pierwiastkiem prymitywnym) to element grupy multiplikatywnej modulo n, którego rząd jest równy rzędowi grupy. W teorii grup oznacza to, że jest to generator grupy – element, który poprzez kolejne potęgowanie generuje wszystkie elementy danej grupy.

Jeśli grupa multiplikatywna modulo n jest cykliczna, to istnieją w niej pierwiastki pierwotne. Potęgując taki element, otrzymuje się kolejno wszystkie elementy grupy.

Przykłady: dla , grupa ma dwa pierwiastki pierwotne: oraz ; dla , pierwiastkami pierwotnymi są oraz ; dla pierwiastki pierwotne nie istnieją – grupa nie jest cykliczna.

Jeśli grupa multiplikatywna modulo n posiada pierwiastki pierwotne, to ich liczba jest równa , gdzie oznacza funkcję Eulera (tocjent).

Wysoki rząd

W odniesieniu do grup multiplikatywnych, zwłaszcza tych o dużym porządku (na przykład rzędu , jak w przypadku generatora liczb pseudolosowych Lehmera), stosuje się pojęcie wysokiego rzędu elementu, nawet jeśli rozpatrywany element nie jest pierwiastkiem pierwotnym.

Określenie „wysoki rząd” nie posiada ścisłej definicji – jest to termin używany intuicyjnie lub opisowo. Oznacza sytuację, w której rząd elementu jest stosunkowo duży w porównaniu z maksymalnym możliwym rzędem w danej grupie.

Przykład: w grupie multiplikatywnej modulo 81 (tj. ), maksymalny rząd elementów (równa się on rzędowi grupy) wynosi 54. Istnieje wiele pierwiastków pierwotnych generujących całą grupę, których rzędy są równe 54.

Jednak inne elementy, względnie pierwsze z 81 (czyli niepodzielne przez 3), mogą mieć rzędy mniejsze, na przykład: – rząd 27 (ciąg: 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 9 (ciąg: 10, 19, 28, 37, 46, 55, 64, 73, 1); – rząd 3 (ciąg: 28, 55, 1).

W powyższym przykładzie element można określić jako element o „wysokim rzędzie”, ponieważ jego rząd (27) jest relatywnie duży w stosunku do rzędu maksymalnego (54), mimo że nie jest pierwiastkiem pierwotnym.

Przykład kodu W celu wyznaczenia rzędów elementów w grupie multiplikatywnej modulo , należy w pierwszej kolejności rozróżnić liczby względnie pierwsze z od pozostałych. W tym celu rozkłada się liczbę na czynniki pierwsze:

.

Na podstawie tego rozkładu można wyznaczyć zbiór liczb całkowitych od 1 do , które są względnie pierwsze z , to znaczy niepodzielne przez żaden z czynników pierwszych liczby . Wyznaczenie tego zbioru można zrealizować na przykład przy użyciu „tablicy binarnej” (tzw. sita), wykreślając wielokrotności każdego z .

Dla każdej liczby względnie pierwszej z można następnie wyznaczyć jej rząd, poprzez potęgowanie modulo – sprawdzając kolejne potęgi elementu aż do momentu uzyskania reszty 1 (co oznacza zakończenie cyklu).

Jeżeli dana liczba generuje wszystkie liczby względnie pierwsze z (czyli wszystkie elementy grupy multiplikatywnej modulo ), to jej rząd jest równy , a liczba ta jest pierwiastkiem pierwotnym modulo . Zobacz przykład programu wyznaczającego rząd w grupie multiplikatywnej na Wikibooks.

Zobacz też arytmetyka modularna logarytm dyskretny rząd (teoria grup)

Przypisy

Kategoria:Teoria grup skończonych Kategoria:Arytmetyka modularna