Tekst źródłowy strony Arytmetyka modularna

{{Inne znaczenia|systemu liczbowego w matematyce|[[modulo|sposoby realizacji]] w informatyce}}

'''Arytmetyka modularna''', '''arytmetyka reszt''' – system [[liczby całkowite|liczb całkowitych]], w którym liczby „zawijają się” po osiągnięciu pewnej wartości nazywanej modułem, często określanej terminem ''modulo'' (skracane ''mod''). Pierwszy pełny wykład arytmetyki reszt przedstawił [[Carl Friedrich Gauss]] w ''Disquisitiones Arithmeticae'' („Badania arytmetyczne”, [[1801]]).

Arytmetyka modularna pojawia się wszędzie tam, gdzie występuje powtarzalność i cykliczność; dotyczy ona samego [[pomiar|mierzenia]] [[czas]]u i jako taka jest podstawą działania [[kalendarz]]a (zob. [[#Motywacja|dalej]]). Ponadto korzysta się z niej w [[teoria liczb|teorii liczb]], [[teoria grup|teorii grup]], [[kryptologia|kryptografii]], [[informatyka|informatyce]], przy tworzeniu [[suma kontrolna|sum kontrolnych]], a nawet przy tworzeniu ornamentów<ref>{{Cytuj | tytuł = Modular Art | opublikowany = britton.disted.camosun.bc.ca | archiwum = https://web.archive.org/web/20060101075602/http://britton.disted.camosun.bc.ca/modart/jbmodart.htm | autor= Jill Britton|data=2005}}</ref>. Zasada działania szyfru [[RSA (kryptografia)|RSA]] oraz [[Test Millera-Rabina]] opierają się na własnościach mnożenia w arytmetyce modularnej liczb całkowitych.

== Motywacja ==
{{Zobacz też|zegar}}
[[Plik:Clock group.svg|thumb|300px|Wskazania [[zegar 12-godzinny|zegara 12-godzinnego]] jako przykład zastosowania arytmetyki modularnej.]]
Przykładem może być zegar 24-godzinny, w którym [[doba]] podzielona jest na 24 godziny numerowane od 0 do 23. Każdej z nich można jednoznacznie przyporządkować okres w ciągu doby, który minął od godziny 0:00 do tej właśnie godziny – np. godzinie 7:00 można przyporządkować okres 7 godzin – można sobie wyobrażać, że w pewnym momencie ustawiono wskazówkę na 7 godzinie. W ten sposób jeśli zegar wskazuje godzinę 20:00, to znaczy, że od godziny 0:00 minęło 20 godzin; podobnie jeśli zegar wskazuje godzinę 8:00, to oznacza, że godzina 0:00 była dokładnie 8 godzin temu.

Jeżeli weźmie się jednak pod uwagę okresy dłuższe niż jedna doba, to wspomniane przyporządkowanie nie jest jedynym możliwym: jeśli teraz jest godzina 0:00, to godzinę 4:00 zegar będzie wskazywać tak po 4 godzinach, jak i po 28 godzinach – ogólnie będzie on wskazywał tę samą godzinę po upływie dowolnej liczby pełnych dób (wielokrotności 24 godzin), czyli: wskazania zegara 24-godzinnego powtarzają się co 24 godziny.

Obserwacje dotyczące wskazań zegara po dwóch okresach umożliwiają określenie wskazania zegara po upływie czasu równego sumie długości tych okresów: jeżeli zegar wskazywał godzinę 0:00 i upłynęło 19 godzin (wskazuje więc on godzinę 19:00), a następnie kolejne 8 godzin (zegar nastawiony na 0:00 wskazywałby po tym czasie godzinę 8:00), to zegar nie będzie wskazywał godziny „27:00”, lecz godzinę 3:00 – tak, jak gdyby od 0:00 minęły tylko 3 godziny.

Można więc wprowadzić następujące ''dodawanie'' wskazań zegara: sumą dwóch godzin jest godzina, którą wskazywałby zegar po upływie okresu od 0:00 do pierwszej z godzin powiększonego o okres, który upłynąłby od 0:00 do drugiej z godzin. Oznacza to, że jeżeli okres jest niemniejszy niż 24 godziny, to zegar wskazywać będzie godzinę równą temu okresowi pomniejszonemu o okres 24 godzin. W ten sposób sumą godzin 12:00 i 21:00 jest godzina 9:00 (a nie 33:00). Cofaniu zegara odpowiadałyby „ujemne” okresy, tym zaś „ujemne” wskazania zegara: okresowi −7 godzin (7 godzin wstecz) odpowiada wskazanie zegara sprzed 7 godzin, gdy wskazuje on w tym momencie godzinę 0:00 – na zegarze 24-godzinnym jest to godzina 17:00. Dlatego też różnicą godzin 3:00 i 4:00 jest godzina 23:00 (a nie −1:00).

Upływ czasu liczy się więc zgodnie z arytmetyką liczb całkowitych, z kolei wskazania zegara są zgodne z ''arytmetyką modularną'' o module 24: mierzenie czasu na zegarze rozpoczyna się o godzinie 0:00 „zerując się” po osiągnięciu 24:00, z kolei gdy wskazówka zegara cofa się mijając godzinę 0:00, zegar wskazuje godzinę wcześniejszą niż 24:00.

W ten sam sposób można rozpatrywać obliczenia na dniach [[tydzień|tygodnia]] (wykonywane modulo 7) lub na [[miesiąc]]ach (modulo 12). Prawa działań na liczbach takie jak ''liczba nieparzysta'' + ''liczba parzysta'' = ''liczba nieparzysta'' (zob. [[parzystość liczb]]) dają się opisać za pomocą arytmetyki modulo 2.

== Wprowadzenie ==
{{Zobacz też|działanie algebraiczne}}
Zgodnie z powyższą intuicją można wprowadzić w zbiorze <math>\{0, 1, \dots, n-1\}</math> uproszczony model arytmetyki modulo <math>n</math> definiując działania:
* dodawania <math>\oplus_n</math> wzorem
*: <math>a \oplus_n b = \begin{cases} a + b, & \mbox{gdy } a + b < n; \\ a + b - n, & \mbox{gdy } a + b \geqslant n; \end{cases}</math>
* brania liczby przeciwnej <math>\ominus_n</math> wzorem
*: <math>\ominus_n c = \begin{cases} -c + n, & \mbox{gdy } c > 0; \\ 0, & \mbox{gdy } c = 0. \end{cases}</math>

W ten sposób uzyskuje się również naturalnie określone działanie
* odejmowania <math>a \ominus_n b := a \oplus_n (\ominus_n b)</math> wzorem
*: <math>a \ominus_n b = \begin{cases} a - b, & \mbox{gdy } a - b \geqslant 0, \mbox{ czyli } a \geqslant b; \\ a - b + n, & \mbox{gdy } a - b < 0, \mbox{ czyli } a < b.\end{cases}</math>

Jak zauważono wyżej dodanie wielokrotności <math>n</math> nie zmienia wyniku działania dodawania (odejmowania) modularnego:
: <math>(a + kn) \oplus_n b = a \oplus_n (b + kn) = a \oplus_n b</math>

dla dowolnych liczb całkowitych <math>a, b, k.</math>

; Przykład:
: Działania te zgodne są z intuicyjnym rozumieniem arytmetyki pomiaru czasu na zegarze 24-godzinnym: dla <math>n = 24</math> zachodzą równości
:* <math>7 \oplus_{24} 8 = 15,</math>
:* <math>3 \ominus_{24} 13 = 3 - 13 + 24 = 14.</math>

Dalej zamiast <math>a \oplus_n b</math> stosowane będzie oznaczenie <math>[a + b]_n,</math> z kolei <math>\ominus_n c</math> będzie oznaczane <math>[-c]_n,</math> gdzie działania dodawania i odejmowania w nawiasach kwadratowych są zwykłymi działaniami arytmetycznymi liczb całkowitych, zaś symbol <math>[\ ]_n</math> oznaczać będzie dodanie bądź odjęcie wielokrotności liczby <math>n</math> tak, by zawartość nawiasu należała do zbioru <math>\{0, \dots, n-1\}.</math> Innymi słowy operacja <math>[c]_n</math> oznacza wzięcie [[twierdzenie o dzieleniu z resztą|reszty z dzielenia]] liczby <math>c</math> przez <math>n.</math>

== Przystawanie ==
{{Zobacz też|kongruencja (algebra)|o1 = przystawanie}}
Relację <math>\equiv_n</math> utożsamiającą ze sobą liczby o tej samej [[twierdzenie o dzieleniu z resztą|reszcie z dzielenia]] przez <math>n,</math> tzn. relację daną wzorem
: <math>a \equiv_n b</math> wtedy i tylko wtedy, gdy <math>[a]_n = [b]_n,</math>

nazywa się '''przystawaniem''' bądź '''kongruencją''' o module (modulo) <math>n.</math> Jeśli liczby <math>a</math> i <math>b</math> dają tę samą resztę z dzielenia przez <math>n,</math> to ich [[odejmowanie|różnica]] <math>a - b</math> jest [[wielokrotność|wielokrotnością]] liczby <math>n</math> lub równoważnie <math>n</math> jest [[dzielnik]]iem <math>a - b.</math> Wspomniane dwa sformułowania są często przyjmowanymi definicjami przystawania<ref>{{Encyklopedia PWN | tytuł = kongruencja | id = 3924985 | data dostępu = 2021-07-21}}</ref>. Innym sposobem zapisu relacji <math>a \equiv_n b</math> jest <math>a = b\ (\bmod\ n),</math> a nawet <math>a = b\ (n).</math> Jeśli nie będzie prowadzić to do nieporozumień, w dalszej części artykułu indeks <math>n</math> przy symbolach <math>[\ ]_n</math> oraz <math>\equiv_n</math> będzie pomijany.

W ten sposób ostatni wzór z powyższej sekcji można zapisać następująco:
: <math>[a + b + kn] = [a + b],</math>

a więc
: <math>a + b + kn \equiv a + b</math>

dla dowolnej liczby całkowitej <math>k.</math> Wzór ten oznacza więc także, że przystawanie utożsamia ze sobą liczby różniące się o [[wielokrotność]] ustalonej liczby <math>n,</math> tzn. dla każdej liczby całkowitej <math>c</math> zachodzi
: <math>c + kn \equiv c,</math>

gdzie <math>k</math> jest dowolną liczbą całkowitą.

; Przykład:
: Jeśli <math>n = 24,</math> to
:: <math>57 \equiv 9,</math>
: gdyż resztą z dzielenia 57 przez 24 oraz 9 przez 24 jest liczba 9; równoważnie
:: <math>[57] = [9],</math>
: ponieważ <math>57 - 9 = 48 = 2 \cdot 24</math> jest podzielne przez <math>24.</math>

W liczbach całkowitych oprócz działania [[dodawanie|dodawania]] i brania [[liczba przeciwna|liczby przeciwnej]] ([[odejmowanie|odejmowania]]) wyróżnione jest działanie [[mnożenie|mnożenia]] (w liczbach całkowitych [[dzielenie]] jest nieokreślone – w ogólności iloraz liczby całkowitej i niezerowej liczby całkowitej nie zawsze jest liczbą całkowitą, zob. [[działanie dwuargumentowe#Działanie wewnętrzne|wewnętrzne działanie dwuargumentowe]]). Oprócz działania dodawania <math>[a + b]</math> ma więc sens rozważanie działanie mnożenia <math>[a \cdot b],</math> można więc przyjąć
: <math>[a \cdot b + kn] = [a \cdot b],</math>

czyli
: <math>a \cdot b + kn \equiv a \cdot b.</math>

Skoro przystawanie utożsamia liczby różniące się o pewną wielokrotność modułu <math>n</math> (tzn. zegar wskazuje tę samą godzinę po upływie wielokrotności 24 godzin), to można wymagać, by wynik dodawania, czy mnożenia nie zależał od wielokrotności modułu, a jedynie od reszty z dzielenia (by wynik działań na wskazaniach zegara nie zależał od czasu, który upłynął, by zegar osiągnął wskazania będące argumentami). Innymi słowy, jeśli zachodzą przystawania
: <math>a \equiv b</math> i <math>c \equiv d,</math>

to
: <math>a + c \equiv b + d</math>

oraz
: <math>ac \equiv bd.</math>

Dla <math>a \equiv b</math> i dowolnej liczby całkowitej <math>c</math> zachodzą ponadto wzory
: <math>a \pm c \equiv b \pm c,</math>

gdyż <math>n</math> dzieli <math>a - b = (a + c) - (b + c) = (a - c) - (b - c)</math> oraz
: <math>ac \equiv bc,</math>

ponieważ skoro <math>n</math> dzieli <math>a - b,</math> to dzieli także <math>c(a - b) = ac - bc.</math>

Powyższe wzory oznaczają więc, że kongruencje o tym samym module można dodawać, odejmować i mnożyć stronami oraz przenosić wyrazy z jednej strony kongruencji na drugą zmieniając przy tym ich znaki. Można również podnieść obie strony kongruencji do tej samej [[potęgowanie|potęgi]] (o naturalnym wykładniku). Niepoprawne jest jednak dzielenie kongruencji stronami, ani skracanie wspólnego dla obu stron dzielnika. Jeśli <math>ad \equiv bd,</math> to <math>n</math> dzieli <math>ad - bd = d(a - b).</math> Jeżeli <math>n</math> i <math>d</math> są [[liczby względnie pierwsze|względnie pierwsze]], to <math>n</math> musi dzielić <math>a - b,</math> a więc <math>a \equiv b.</math> Zatem dzielenie obu stron przez wspólny dzielnik jest poprawne jedynie wtedy, gdy jest on względnie pierwszy z modułem.

== Pierścień klas reszt ==
=== Klasy reszt ===
{{Zobacz też|relacja równoważności}}
Niech <math>a, b, c</math> będą dowolnymi liczbami całkowitymi. Kongruencja modulo <math>n</math> jest relacją równoważności, tzn. jest
* [[relacja zwrotna|zwrotna]]:
*: <math>a \equiv a,</math>
* [[relacja symetryczna|symetryczna]]:
*: <math>a \equiv b</math> pociąga <math>b \equiv a,</math>
* [[relacja przechodnia|przechodnia]]:
*: jeśli <math>a \equiv b</math> oraz <math>b \equiv c,</math> to <math>a \equiv c.</math>

Jak każda relacja równoważności, przystawanie wprowadza [[Rozbicie zbioru|Podział zbioru]] (w tym wypadku liczb całkowitych) na [[podzbiór|podzbiory]] nazywane '''klasami reszt''' lub '''klasami kongruencji''', które zawierają liczby dające tę samą resztę z dzielenia przez moduł i różniące się przy tym o jego wielokrotność; klas jest tyle, ile wynosi moduł przystawania. W dalszym ciągu podzbiory te będą oznaczane symbolem <math>[i],</math> gdzie <math>i</math> jest dowolną liczbą należącą do tego zbioru nazywaną ''reprezentantem'' tej klasy (zwykle jest nią najmniejsza nieujemna liczba z tego zbioru). Z własności relacji równoważności każda liczba całkowita należy do dokładnie jednej klasy reszt.

=== Działania ===
{{Zobacz też|pierścień (matematyka)|o1=pierścień}}
Dwie klasy reszt dodaje się wybierając z każdej z nich po jednym reprezentancie, odpowiednio <math>x</math> oraz <math>y;</math> wynikiem jest klasa reszt, do której należy <math>x + y.</math> Okazuje się, że wynik takiego dodawania [[relacja równoważności#Niezależność|nie zależy od wyboru reprezentantów]] <math>x</math> i <math>y.</math>

; Przykład:
: Jeśli <math>n = 4,</math> to klasy reszt są zbiorami:
:: <math>[0] := \{\dots, -4, 0, 4, 8, 12, \dots\},</math>
:: <math>[1] := \{\dots, -3, 1, 5, 9, 13, \dots\},</math>
:: <math>[2] := \{\dots, -2, 2, 6, 10, 14, \dots\},</math>
:: <math>[3] := \{\dots, -1, 3, 7, 11, 15, \dots\}.</math>
: Chcąc dodać <math>[2]</math> do <math>[3]</math> wystarczy wybrać po jednym elemencie z każdej z nich, np. <math>2</math> i <math>7</math> – wynikiem jest klasa zawierająca <math>2 + 7 = 9,</math> tzn. klasa <math>[9] = [1].</math> Jeżeli wybrać przy dodawaniu <math>10</math> i <math>3,</math> to wynik byłby taki sam: ta sama klasa reszt zawiera liczbę <math>13.</math>

W taki sam sposób można zdefiniować mnożenie, które również jest określone jednoznacznie.

Przedstawione wyżej działania na klasach reszt mają regularne własności:
* dodawanie i mnożenie jest [[przemienność|przemienne]] i [[łączność (matematyka)|łączne]];
* dodawanie ma [[element neutralny]] <math>[0] = \{\dots, -2n, -n, 0, n, 2n, \dots\};</math>
* mnożenie ma element neutralny <math>[1] = \{\dots, -n+1, 1, n+1, 2n+1, \dots\};</math>
* mnożenie jest [[Rozdzielność|rozdzielne]] względem dodawania.

Struktura o tych własnościach nazywana jest [[pierścień przemienny|pierścieniem przemiennym]] [[pierścień z jedynką|z jedynką]].

=== Definicja ===
{{Zobacz też|pierścień ilorazowy}}
Niech <math>\equiv</math> będzie relacją przystawania modulo <math>n,</math> gdzie <math>n</math> jest dowolną nieujemną liczbą całkowitą. Niech <math>[a]</math> oznacza [[relacja równoważności|klasę abstrakcji]] odpowiadającą liczbie <math>a.</math> W [[Przestrzeń ilorazowa (algebra liniowa)|zbiorze ilorazowym]] <math>\mathbb Z/\equiv</math> wprowadza się działania dodawania i mnożenia klas reszt (dziedziczone z [[pierścień liczb całkowitych|pierścienia liczb całkowitych]]) wzorami
: <math>[a] \oplus [b] = [a + b],</math>
: <math>[a] \odot [b] = [a \cdot b].</math>

Zbiór <math>\mathbb Z/\equiv</math> wraz z działaniami <math>\oplus</math> i <math>\odot</math> nazywa się '''pierścieniem klas reszt''' modulo <math>n</math> i oznacza symbolami <math>\mathbb Z_n</math> lub <math>\mathbb Z(n),</math> przy czym symbole <math>\oplus</math> i <math>\odot</math> zastępuje się zwykle zwyczajowymi <math>+</math> oraz <math>\cdot,</math> co zostanie uczynione w dalszej części artykułu. Ponadto podając elementy pierścienia <math>\mathbb Z_n</math> opuszcza się niekiedy nawiasy i wybiera najmniejszego nieujemnego reprezentanta, tj. liczbę ze zbioru <math>\{0, 1, \dots, n-1\},</math> którą można znaleźć biorąc resztę z dzielenia dowolnego reprezentanta przez <math>n.</math> Innymi słowy utożsamia się w naturalny sposób elementy pierścienia <math>\mathbb Z_n</math> z odpowiadającymi im elementami pierścienia <math>\mathbb Z.</math>

Na mocy [[grupa ilorazowa#Twierdzenie o homomorfizmie (faktoryzacji)|twierdzenia o homomorfizmie]] dla pierścieni operator <math>[\ ]_n</math> brania klas reszt modulo <math>n</math> jest [[homomorfizm]]em pierścienia <math>\mathbb Z</math> w pierścień <math>\mathbb Z_n,</math> który przypisuje liczbie całkowitej jej resztę z dzielenia przez <math>n.</math> [[Jądro (algebra)|Jądrem]] tego homomorfizmu jest [[ideał (teoria pierścieni)|ideał]] <math>n\mathbb Z,</math> czyli wszystkie liczby podzielne przez <math>n,</math> zaś [[Obraz (matematyka)|obrazem]] są liczby ze zbioru <math>\{0, \dots, n-1\}.</math> To samo twierdzenie o homomorfizmie zapewnia, że iloraz <math>\mathbb Z</math> przez <math>n\mathbb Z</math> jest [[izomorfizm|izomorficzny]] z wyżej zdefiniowanym pierścieniem klas reszt modulo <math>n.</math> Stąd też pochodzi alternatywne oznaczenie <math>\mathbb Z/n\mathbb Z</math> tego pierścienia; ponieważ ideał <math>n\mathbb Z</math> oznacza się również symbolem <math>(n),</math> to spotyka się również oznaczenie <math>\mathbb Z/(n).</math> W ten sposób konstrukcje dzielenia pierścienia liczb całkowitych przez relację przystawania modulo <math>n</math> i dzielenia go przez ideał <math>n\mathbb Z</math> są równoważne z punktu widzenia algebry.

Pierścień <math>\mathbb Z_0</math> jest izomorficzny z pierścieniem <math>\mathbb Z,</math> przypadek ten omawia się szerzej w artykule dotyczącym [[liczby całkowite|liczb całkowitych]].

=== Własności ===
[[Element neutralny|Elementem neutralnym]] dodawania w <math>\mathbb Z_n</math> jest <math>[0],</math> [[Element odwrotny|elementem przeciwnym]] do <math>[k]</math> jest <math>[-k] = [n-k],</math> elementem neutralnym mnożenia jest <math>[1].</math>

Element <math>[k]</math> pierścienia <math>\mathbb Z_n</math> jest [[element odwracalny|odwracalny]] wtedy i tylko wtedy, gdy liczba całkowita <math>k</math> jest [[liczby względnie pierwsze|względnie pierwsza]] z <math>n.</math> Wynika to z faktu, iż można dobrać takie liczby całkowite <math>a, b,</math> dla których zachodzi <math>an + bk = 1;</math> wtedy <math>bk \equiv 1,</math> czyli <math>[b][k] = 1,</math> co oznacza, iż <math>[k]</math> ma odwrotność <math>[b].</math> Jeżeli <math>n</math> i <math>k</math> mają wspólny dzielnik <math>a > 1,</math> tj. <math>n = ab,</math> i <math>k = ac,</math> to <math>[k][b] = [ac][b] = [abc] = 0,</math> co oznacza, że <math>[k]</math> jest [[dzielnik zera|dzielnikiem zera]].

Wynika stąd, że jeżeli <math>n</math> jest [[Liczby pierwsze|liczbą pierwszą]], to w pierścieniu <math>\mathbb Z_n</math> jedynym dzielnikiem zera jest <math>[0].</math> W przeciwnym wypadku istnieją nietrywialne dzielniki zera. Dlatego pierścień <math>\mathbb Z_n</math> jest [[ciało (matematyka)|ciałem]] wtedy i tylko wtedy, gdy <math>n</math> jest liczbą pierwszą.

[[Charakterystyka (algebra)|Charakterystyka]] pierścienia <math>\mathbb Z_n</math> jest równa <math>n.</math> Każdą [[grupa przemienna|grupę abelową]] o [[skończenie generowana grupa przemienna|skończonej liczbie generatorów]] można przedstawić jako [[iloczyny grup#Suma prosta|sumę prostą]] grup <math>\mathbb Z_n</math> (zob. [[skończenie generowana grupa przemienna#Klasyfikacja|twierdzenie]]).

=== Grupa addytywna ===
{{osobny artykuł|grupa addytywna}}
[[Grupa addytywna]] pierścienia <math>(\mathbb Z_n, +, \cdot),</math> tj. <math>(\mathbb Z_n, +)</math> jest [[grupa (matematyka)|grupą]] [[grupa cykliczna|cykliczną]] zwaną '''addytywną grupą klas reszt''' modulo <math>n.</math> W [[teoria grup|teorii grup]] oznacza się ją symbolami <math>\mathbb Z_n</math> lub <math>\mathbb Z/n\mathbb Z.</math>

Generatorem tej grupy jest dowolna liczba względnie pierwsza z <math>n.</math> Co więcej, z dokładnością do [[izomorfizm]]u, jedynymi grupami cyklicznymi są <math>(\mathbb Z_n, +)</math> i grupa addytywna liczb całkowitych.

Prawdziwa jest też równość dotycząca [[rząd (teoria grup)|rzędu elementu]]:
: <math>\operatorname{o}(g) = \tfrac{n}{\operatorname{nwd}(g, n)},</math>

gdzie <math>\operatorname{nwd}</math> oznacza [[największy wspólny dzielnik]].

=== Grupa multiplikatywna ===
{{osobny artykuł|grupa multiplikatywna}}
Elementami odwracalnymi pierścienia <math>\mathbb Z_n</math> są te liczby ze zbioru <math>\{0, 1, \dots, n-1\},</math> które są względnie pierwsze z <math>n{:}</math>
: <math>\mathbb{Z}_n^* = \big\{[a]\colon \operatorname{nwd}(a, n) = 1\big\}.</math>

Ich liczbę wyznacza [[funkcja φ]] Eulera. W szczególności, <math>\varphi(n) = n-1 \Leftrightarrow n \in \mathbb P \Leftrightarrow \mathbb Z_n</math> jest ciałem.

Te elementy tworzą grupę, zwaną '''multiplikatywną grupą klas reszt''' modulo <math>n.</math> Oznaczana jest <math>\mathbb Z_n^*,</math> <math>U(\mathbb Z_n)</math> lub <math>(\mathbb Z/n\mathbb Z)^*.</math>

Element <math>a</math> jest [[Grupa (matematyka)#Zbiór generatorów|generatorem]] grupy <math>\mathbb Z_n^*</math> wtedy i tylko wtedy, gdy liczba <math>a</math> jest [[Pierwiastek pierwotny|pierwiastkiem pierwotnym]] liczby <math>n.</math> Grupa <math>\mathbb Z_n^*</math> jest zatem cykliczna wtedy i tylko wtedy, gdy liczba <math>n</math> posiada pierwiastek pierwotny, a to zachodzi dokładnie wtedy, gdy <math>n= 2, 4,</math> gdy <math>n</math> jest [[Potęgowanie|potęgą]] nieparzystej liczby pierwszej (to znaczy postaci <math>p^\alpha,</math> <math>p</math>-nieparzysta liczba pierwsza) lub podwojoną potęgą nieparzystej liczby pierwszej (to znaczy postaci <math>2p^\alpha,</math> <math>p</math>-nieparzysta liczba pierwsza)<ref>[http://matwbn.icm.edu.pl/ksiazki/mon/mon19/mon1908.pdf Wacław Sierpiński, ''Teoria Liczb'', Monografie Matematyczne 19, rozdział VIII].</ref>. Tak więc grupa <math>\mathbb Z_n^*</math> jest cykliczna dla <math>n=2,3,4,5,6,7,9,10,11,13,14,17,18,19,22,23,25,26,27,29,31</math> itd.

=== Pierwiastki kwadratowe z jedności ===
{{Zobacz też|pierwiastek z jedynki}}
'''Pierwiastkiem kwadratowym z jedności''' modulo <math>n</math> nazywa się taki element <math>k \in \mathbb Z_n,</math> dla którego zachodzi
: <math>k^2 = 1.</math>

W dowolnym pierścieniu <math>\mathbb Z_n</math> pierwiastkami z jedności są <math>1</math> i <math>-1.</math> Można udowodnić, że liczba wszystkich pierwiastków kwadratowych modulo <math>n</math> wynosi{{odn|Graham|Knuth|Patashnik|2006|s=154}}:
: <math>2^{f(n)+[8|n]-[2|n]+[4|n]}.</math>

gdzie:
* <math>[x|y]</math> jest równe 1, gdy <math>x</math> jest dzielnikiem <math>y,</math> 0, jeżeli nie jest;
* <math>f(n)</math> jest liczbą pierwszych dzielników <math>n.</math>

Aby sprawdzić, czy równanie <math>a^2=x</math> ma rozwiązanie, można skorzystać z własności [[symbol Jacobiego|symbolu Jacobiego]].

; Przykład:
: W pierścieniu <math>\mathbb Z_{60}</math> jest <math>2^{3 + 0 - 1 + 1} = 2^3 = 8</math> [[Pierwiastek z jedynki|pierwiastków z jedynki]]:
:* <math>1 \mapsto 1^2 \equiv 1,</math>
:* <math>11 \mapsto 11^2 = 121 \equiv 1,</math>
:* <math>19 \mapsto 19^2 = 361 \equiv 1,</math>
:* <math>29 \mapsto 29^2 = 841 \equiv 1,</math>
:* <math>31 \mapsto 31^2 \equiv (-29)^2 \equiv 1,</math>
:* <math>41 \mapsto 41^2 \equiv (-19)^2 \equiv 1,</math>
:* <math>49 \mapsto 49^2 \equiv (-11)^2 \equiv 1,</math>
:* <math>59 \mapsto 59^2 \equiv (-1)^2 \equiv 1.</math>

== Zobacz też ==
* [[Blum Blum Shub]]
* [[cecha podzielności]]
* [[logarytm dyskretny]]
* [[małe twierdzenie Fermata]]

== Przypisy ==
{{Przypisy}}

== Bibliografia ==
* {{cytuj książkę | nazwisko = Graham | imię = Ronald L. | nazwisko2 = Knuth | imię2 = Donald E. | autor link2 = Donald Knuth | nazwisko3 = Patashnik | imię3 = Oren | tytuł = Matematyka konkretna | miejsce = Warszawa | wydawca = [[Wydawnictwo Naukowe PWN]] | rok = 2006 | isbn = 83-01-14764-4 | odn = tak}}

== Linki zewnętrzne ==
* {{MathWorld | adres = ModularArithmetic | tytuł = Modular Arithmetic}} [dostęp 2024-02-02].
* {{otwarty dostęp}} ''[https://encyclopediaofmath.org/wiki/Congruence Congruence]'' {{lang|en}}, Encyclopedia of Mathematics, encyclopediaofmath.org [dostęp 2024-05-30].

{{Działy arytmetyki}}
{{Teoria liczb}}
{{Teoria grup}}

{{Kontrola autorytatywna}}

[[Kategoria:Arytmetyka modularna| ]]
[[Kategoria:Komputerowe reprezentacje danych]]
[[Kategoria:Dwuczłonowe relacje matematyczne]]