Arytmetyka modularna

teoria skończonych grup cyklicznych

Arytmetyka modularna, arytmetyka reszt – system 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 mierzenia czasu i jako taka jest podstawą działania kalendarza (zob. dalej). Ponadto korzysta się z niej w teorii liczb, teorii grup, kryptografii, informatyce, przy tworzeniu sum kontrolnych, a nawet przy tworzeniu wzorów[1]. Zasada działania szyfru RSA oraz Test Millera-Rabina opierają się na własnościach mnożenia w arytmetyce modularnej liczb całkowitych.

Motywacja edytuj

Zobacz też: zegar.
 
Wskazania 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 tygodnia (wykonywane modulo 7) lub na miesiącach (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 edytuj

Zgodnie z powyższą intuicją można wprowadzić w zbiorze   uproszczony model arytmetyki modulo   definiując działania:

  • dodawania   wzorem
     
  • brania liczby przeciwnej   wzorem
     

W ten sposób uzyskuje się również naturalnie określone działanie

  • odejmowania   wzorem
     

Jak zauważono wyżej dodanie wielokrotności   nie zmienia wyniku działania dodawania (odejmowania) modularnego:

 

dla dowolnych liczb całkowitych  

Przykład
Działania te zgodne są z intuicyjnym rozumieniem arytmetyki pomiaru czasu na zegarze 24-godzinnym: dla   zachodzą równości
  •  
  •  

Dalej zamiast   stosowane będzie oznaczenie   z kolei   będzie oznaczane   gdzie działania dodawania i odejmowania w nawiasach kwadratowych są zwykłymi działaniami arytmetycznymi liczb całkowitych, zaś symbol   oznaczać będzie dodanie bądź odjęcie wielokrotności liczby   tak, by zawartość nawiasu należała do zbioru   Innymi słowy operacja   oznacza wzięcie reszty z dzielenia liczby   przez  

Przystawanie edytuj

Zobacz też: przystawanie.

Relację   utożsamiającą ze sobą liczby o tej samej reszcie z dzielenia przez   tzn. relację daną wzorem

  wtedy i tylko wtedy, gdy  

nazywa się przystawaniem bądź kongruencją o module (modulo)   Jeśli liczby   i   dają tę samą resztę z dzielenia przez   to ich różnica   jest wielokrotnością liczby   lub równoważnie   jest dzielnikiem   Wspomniane dwa sformułowania są często przyjmowanymi definicjami przystawania[2]. Innym sposobem zapisu relacji   jest   a nawet   Jeśli nie będzie prowadzić to do nieporozumień, w dalszej części artykułu indeks   przy symbolach   oraz   będzie pomijany.

W ten sposób ostatni wzór z powyższej sekcji można zapisać następująco:

 

a więc

 

dla dowolnej liczby całkowitej   Wzór ten oznacza więc także, że przystawanie utożsamia ze sobą liczby różniące się o wielokrotność ustalonej liczby   tzn. dla każdej liczby całkowitej   zachodzi

 

gdzie   jest dowolną liczbą całkowitą.

Przykład
Jeśli   to
 
gdyż resztą z dzielenia 57 przez 24 oraz 9 przez 24 jest liczba 9; równoważnie
 
ponieważ   jest podzielne przez  

W liczbach całkowitych oprócz działania dodawania i brania liczby przeciwnej (odejmowania) wyróżnione jest działanie 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. wewnętrzne działanie dwuargumentowe). Oprócz działania dodawania   ma więc sens rozważanie działanie mnożenia   można więc przyjąć

 

czyli

 

Skoro przystawanie utożsamia liczby różniące się o pewną wielokrotność modułu   (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

  i  

to

 

oraz

 

Dla   i dowolnej liczby całkowitej   zachodzą ponadto wzory

 

gdyż   dzieli   oraz

 

ponieważ skoro   dzieli   to dzieli także  

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ęgi (o naturalnym wykładniku). Niepoprawne jest jednak dzielenie kongruencji stronami, ani skracanie wspólnego dla obu stron dzielnika. Jeśli   to   dzieli   Jeżeli   i  względnie pierwsze, to   musi dzielić   a więc   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 edytuj

Klasy reszt edytuj

Niech   będą dowolnymi liczbami całkowitymi. Kongruencja modulo   jest relacją równoważności, tzn. jest

  • zwrotna:
     
  • symetryczna:
      pociąga  
  • przechodnia:
    jeśli   oraz   to  

Jak każda relacja równoważności, przystawanie wprowadza Podział zbioru (w tym wypadku liczb całkowitych) na 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   gdzie   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 edytuj

Zobacz też: pierścień.

Dwie klasy reszt dodaje się wybierając z każdej z nich po jednym reprezentancie, odpowiednio   oraz   wynikiem jest klasa reszt, do której należy   Okazuje się, że wynik takiego dodawania nie zależy od wyboru reprezentantów   i  

Przykład
Jeśli   to klasy reszt są zbiorami:
 
 
 
 
Chcąc dodać   do   wystarczy wybrać po jednym elemencie z każdej z nich, np.   i   – wynikiem jest klasa zawierająca   tzn. klasa   Jeżeli wybrać przy dodawaniu   i   to wynik byłby taki sam: ta sama klasa reszt zawiera liczbę  

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 przemienne i łączne;
  • dodawanie ma element neutralny  
  • mnożenie ma element neutralny  
  • mnożenie jest rozdzielne względem dodawania.

Struktura o tych własnościach nazywana jest pierścieniem przemiennym z jedynką.

Definicja edytuj

Zobacz też: pierścień ilorazowy.

Niech   będzie relacją przystawania modulo   gdzie   jest dowolną nieujemną liczbą całkowitą. Niech   oznacza klasę abstrakcji odpowiadającą liczbie   W zbiorze ilorazowym   wprowadza się działania dodawania i mnożenia klas reszt (dziedziczone z pierścienia liczb całkowitych) wzorami

 
 

Zbiór   wraz z działaniami   i   nazywa się pierścieniem klas reszt modulo   i oznacza symbolami   lub   przy czym symbole   i   zastępuje się zwykle zwyczajowymi   oraz   co zostanie uczynione w dalszej części artykułu. Ponadto podając elementy pierścienia   opuszcza się niekiedy nawiasy i wybiera najmniejszego nieujemnego reprezentanta, tj. liczbę ze zbioru   którą można znaleźć biorąc resztę z dzielenia dowolnego reprezentanta przez   Innymi słowy utożsamia się w naturalny sposób elementy pierścienia   z odpowiadającymi im elementami pierścienia  

Na mocy twierdzenia o homomorfizmie dla pierścieni operator   brania klas reszt modulo   jest homomorfizmem pierścienia   w pierścień   który przypisuje liczbie całkowitej jej resztę z dzielenia przez   Jądrem tego homomorfizmu jest ideał   czyli wszystkie liczby podzielne przez   zaś obrazem są liczby ze zbioru   To samo twierdzenie o homomorfizmie zapewnia, że iloraz   przez   jest izomorficzny z wyżej zdefiniowanym pierścieniem klas reszt modulo   Stąd też pochodzi alternatywne oznaczenie   tego pierścienia; ponieważ ideał   oznacza się również symbolem   to spotyka się również oznaczenie   W ten sposób konstrukcje dzielenia pierścienia liczb całkowitych przez relację przystawania modulo   i dzielenia go przez ideał   są równoważne z punktu widzenia algebry.

Pierścień   jest izomorficzny z pierścieniem   przypadek ten omawia się szerzej w artykule dotyczącym liczb całkowitych.

Własności edytuj

Elementem neutralnym dodawania w   jest   elementem przeciwnym do   jest   elementem neutralnym mnożenia jest  

Element   pierścienia   jest odwracalny wtedy i tylko wtedy, gdy liczba całkowita   jest względnie pierwsza z   Wynika to z faktu, iż można dobrać takie liczby całkowite   dla których zachodzi   wtedy   czyli   co oznacza, iż   ma odwrotność   Jeżeli   i   mają wspólny dzielnik   tj.   i   to   co oznacza, że   jest dzielnikiem zera.

Wynika stąd, że jeżeli   jest liczbą pierwszą, to w pierścieniu   jedynym dzielnikiem zera jest   W przeciwnym wypadku istnieją nietrywialne dzielniki zera. Dlatego pierścień   jest ciałem wtedy i tylko wtedy, gdy   jest liczbą pierwszą.

Charakterystyka pierścienia   jest równa   Każdą grupę abelową o skończonej liczbie generatorów można przedstawić jako sumę prostą grup   (zob. twierdzenie).

Grupa addytywna edytuj

Osobny artykuł: grupa addytywna.

Grupa addytywna pierścienia   tj.   jest grupą cykliczną zwaną addytywną grupą klas reszt modulo   W teorii grup oznacza się ją symbolami   lub  

Generatorem tej grupy jest dowolna liczba względnie pierwsza z   Co więcej, z dokładnością do izomorfizmu, jedynymi grupami cyklicznymi są   i grupa addytywna liczb całkowitych.

Prawdziwa jest też równość dotycząca rzędu elementu:

 

gdzie   oznacza największy wspólny dzielnik.

Grupa multiplikatywna edytuj

Osobny artykuł: grupa multiplikatywna.

Elementami odwracalnymi pierścienia   są te liczby ze zbioru   które są względnie pierwsze z  

 

Ich liczbę wyznacza funkcja φ Eulera. W szczególności,   jest ciałem.

Te elementy tworzą grupę, zwaną multiplikatywną grupą klas reszt modulo   Oznaczana jest     lub  

Element   jest generatorem grupy   wtedy i tylko wtedy, gdy liczba   jest pierwiastkiem pierwotnym liczby   Grupa   jest zatem cykliczna wtedy i tylko wtedy, gdy liczba   posiada pierwiastek pierwotny, a to zachodzi dokładnie wtedy, gdy   gdy   jest potęgą nieparzystej liczby pierwszej (to znaczy postaci    -nieparzysta liczba pierwsza) lub podwojoną potęgą nieparzystej liczby pierwszej (to znaczy postaci    -nieparzysta liczba pierwsza)[3]. Tak więc grupa   jest cykliczna dla   itd.

Pierwiastki kwadratowe z jedności edytuj

Zobacz też: pierwiastek z jedynki.

Pierwiastkiem kwadratowym z jedności modulo   nazywa się taki element   dla którego zachodzi

 

W dowolnym pierścieniu   pierwiastkami z jedności są   i   Można udowodnić, że liczba wszystkich pierwiastków kwadratowych modulo   wynosi[4]:

 

gdzie:

  •   jest równe 1, gdy   jest dzielnikiem   0, jeżeli nie jest;
  •   jest liczbą pierwszych dzielników  

Aby sprawdzić, czy równanie   ma rozwiązanie, można skorzystać z własności symbolu Jacobiego.

Przykład
W pierścieniu   jest   pierwiastków z jedynki:
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  

Zobacz też edytuj

Przypisy edytuj

  1. Modular Art. britton.disted.camosun.bc.ca. [zarchiwizowane z tego adresu (2006-01-01)]..
  2. kongruencja, [w:] Encyklopedia PWN [dostęp 2021-07-21].
  3. Wacław Sierpiński, Teoria Liczb, Monografie Matematyczne 19, rozdział VIII.
  4. Graham, Knuth i Patashnik 2006 ↓, s. 154.

Bibliografia edytuj

Linki zewnętrzne edytuj