Michał Śliwiński, Grupy i ciała w arytmetyce modularnej

 

Zbiór {0,1,2,...,n-1} oznacza się często przez Zn. Na jego elementach można wykonywać działania modulo n, tzn. z wyników brać reszty z dzielenia przez n (jak wszyscy wiedzą, tworzą one właśnie ten zbiór).

 

Np.:

 

kilka działań w zbiorze Z7 (={0,1,2,3,4,5,6}): 2+3=5, 3+4=0, 4+4=1, 5+2=0, 6+4=3, 2-5=4 (tak, tak – liczba -3 daje przy dzieleniu przez 7 resztę 4 (bo -3=(-1)×7+4, podobnie jak np. 11=1×7+4 – też reszta 4), zauważmy przy okazji, że dzięki temu odejmowanie modulo jest działaniem odwrotnym do dodawania modulo: 2-5 to taka liczba (oczywiście przy działaniach modulo 7 cały czas mówimy o elementach Z7), która dodana do 5 da 2, czyli... 4! J), 2×5=3, 5×5=4,

 

działania modulo 2 (w Z2) są Wam już dobrze znane, jest ich zresztą tak mało, że można wypisać wszystkie możliwe np. dodawania: 0+0=0, 0+1=1, 1+0=1, 1+1=0, z mnożeniami jest chyba jeszcze prościej... J

 

tabliczka dodawania w Z6:

+6

0

1

2

3

4

5

0

0

1

2

3

4

5

1

1

2

3

4

5

0

2

2

3

4

5

0

1

3

3

4

5

0

1

2

4

4

5

0

1

2

3

5

5

0

1

2

3

4

 

(prawda, jaka ładna? w każdym razie widać (mam nadzieję!) pewne regularności i bardzo łatwo się ją konstruuje, całkiem bezmyślnie (niektórzy mogą woleć używać może bardziej wysublimowanego słowa „automatycznie”) – popróbuj z dodawaniem modulo 5;

przy okazji: działania modulo oznacza się czasem, jak widać, odpowiednim indeksikiem, czasem też pisze się w nawiasie po wyniku np. „mod 5”, ale gdy wiadomo, modulo co rachujemy, często się nijak tego specjalnie nie zaznacza)

 

tabliczka mnożenia w Z5:

×5

0

1

2

3

4

0

0

0

0

0

0

1

0

1

2

3

4

2

0

2

4

1

3

3

0

3

1

4

2

4

0

4

3

2

1

 

(jak to zwykle w życiu bywa, mnożenie jest już kapkę trudniejsze, ale za to łatwo mnoży się oczywiście przez 0 i 1! J a bystre oko również tu dostrzeże pewne regularności, chociaż czy tak samo jest też dla innych Zn? (podpowiedź: nie! – pomyśl albo czytaj dalej)).

 

Arytmetykę modularną, jak to się strasznie uczenie nazywa, wykorzystujemy na co dzień (uwaga: „na co dzień” – 3 osobno pisane słowa!!) np. przy określaniu godziny – oczywiste już dla niektórych przedszkolaków jest, że trzy godziny po dziesiątej jest pierwsza, czyli 10+3=1, działamy więc oczywiście modulo 12, ew. 24.

Tak samo można zapisywać nasze rozważania o działaniach na liczbach naturalnych zapisywanych np. na 1 B: tam 255+1=0 albo np. 200+100=100+200=44 (działamy więc oczywiście modulo 256).

 

Zauważmy, że dla każdego n w zbiorze Zn można wprowadzić odejmowanie – dla dowolnych a,bÎZn w Zn istnieje, i to dokładnie jedno (czyli ni mniej, ni więcej niż 1), takie x, że a+x=b (mod n), czyli można powiedzieć, że x=b-a (mod n).

Zauważyć to można z tabelki dodawania – w każdym wierszu występują wszystkie elementy zbioru Zn, i każdy tylko raz. To oczywiście nie dowód, ale popatrzmy jeszcze na przykład:

powiedzmy, że w Z6 chcemy znaleźć różnicę 3 i 5. Oznacza to, że szukamy rozwiązania równania x+5=3 (mod 6). Jak je znaleźć? Mając tabelkę, bardzo prosto: w kolumnie z 5 szukamy trójki. Jest! Konkretnie jest w wierszu 4 (i tylko tam!). Oznacza to więc, że 4+5=3 (mod 6) i możemy napisać 4=3-5 (mod 6).

 

Dla dociekliwych pełny dowód wykonywalności odejmowania modulo n:

Przypominam, że sprowadza się to do wykazania, że równanie a+x=b (mod n) ma w Zn dokładnie jedno rozwiązanie dla dowolnych a i b. Zauważmy, że liczby a, a+1, a+2, ..., a+(n-1) (przy normalnym dodawaniu) to n kolejnych liczb całkowitych, dają one zatem wszystkie reszty z dzielenia przez n i każdą tylko raz (bo jest ich właśnie n). Zatem dodając liczby 0, 1, 2, ..., n-1 do a, uzyskamy resztę b dokładnie raz i ta liczba, po dodaniu której do a uzyskaliśmy resztę b, jest właśnie szukanym x, czyli różnicą b i a. Zauważmy przy okazji, że jest to (n-a)+b (mod n) – modulo n mamy przecie: a+(n-a)+b = 0+b = b, jest więc od razu wzór na różnicę: b-a = (n-a)+b.

 

Gorzej jest niestety z dzieleniem. Pisząc b:a, mamy na myśli taki (jedyny) x, że x×a=b. Oczywiście nie dzielimy przez 0, bo wówczas widać od razu, że takich x nie ma wcale (przy b¹0) lub że każdy x to równanie spełnia (jeśli b też jest zerem). Sprawdźmy więc, że np. równanie x×3=2 ma w Z5 rozwiązanie – w kolumnie 3 tabliczki mnożenia występuje dwójka – konkretnie w wierszu 4, zatem 4×3=2 (co można też sprawdzić, obliczając resztę z dzielenia 4×3 przez 5). Jest to w dodatku jedyne rozwiązanie – dwójka jest w kolumnie 4 tylko raz, można zatem napisać 4=2:3 (mod 5). Zauważmy też, że w każdej kolumnie (poza 0) tabliczki mnożenia modulo 5 występują wszystkie elementy Z5, wszystkie, więc każdy tylko raz (bo jest ich n, tyle co wierszy tabelki), zatem w Z5 można dzielić, byle nie przez 0.

Okazuje się jednak, że już np. w Z6 (ani też choćby w Z4 czy Z9) dzielenia nie można wprowadzić!...  Popatrzmy:

×6

0

1

2

3

4

5

0

0

0

0

0

0

0

1

0

1

2

3

4

5

2

0

2

4

0

2

4

3

0

3

0

3

0

3

4

0

4

2

0

4

2

5

0

5

4

3

2

1

 

- tylko kolumny 1 i 5 mają pożądaną przez nas własność! Oznacza to, że np. działanie 2:3 (mod 6) nie ma sensu. Sprawdźmy: szukamy rozwiązań równania x×3=2 (oczywiście modulo 6), ale w kolumnie 3 nie ma ani jednej dwójki! (Nie tylko zresztą dwójki, jak zauważy baczny obserwator). Równanie to nie ma zatem rozwiązania, czyli taki iloraz nie istnieje. Ale może być też inaczej (w pewnym sensie gorzej): szukając ilorazu 2:2, czyli rozwiązując równanie x×2=2, natkniemy się na 2 rozwiązania – w kolumnie 2 są dwie dwójki! (jedno rozwiązanie (jedynka) było zresztą oczywiste: 1×q daje q dla każdego q). „Działanie” 2:2 (mod 6) nie jest więc działaniem J – nie da się ustalić jego wyniku (chyba żeby wprowadzić jakieś dodatkowe ograniczenia). I nie jest to wina faktu, że dzielna i dzielnik są akurat takie same. Zobaczmy, że nie da się też podzielić 4:2 (dwa „wyniki” – jeden oczywisty – dwójka, a drugi zaleźć można jako numer drugiego wiersza tabeli, który ma w kolumnie 2 czwórkę (czyli 5), zatem poszukiwane rozwiązania równania x×2=4 ma modulo 6 dwa rozwiązania: 2 i 5) ani 2:4 (znów dwie liczby pomnożone przez 4 dają 2 – też zresztą 2 i 5).

Okazuje się, że dzielenie modulo n można tak naturalnie zdefiniować, tylko gdy n jest liczbą pierwszą. Dociekliwym mogę podać dowód tego faktu, ale nie piszę go tu teraz, bo choć nie jest trudny, znacznie lepiej opowiedzieć go ustnie.

 

 

Na koniec jeszcze kilka spostrzeżeń i suchych faktów:

§  dodawanie modulo n ma własności normalnego dodawania:

-        jest łączne (co też wymaga dowodu – chodzi tu o reszty z dzielenia, więc wcale nie jest to tak oczywiste, ale intuicyjnie chyba dość oczekiwane),

-        przemienne (tego dowieść już łatwo – po prostu najpierw normalnie dodajemy, co można zrobić w dowolnej kolejności, a potem obliczamy resztę, mając w obu przypadkach ten sam wynik), a dzięki temu tabelka dodawania jest taka symetryczna... J

-        ma element neutralny (zero – tak jak w zwykłym dodawaniu podziałanie na nim nie zmienia drugiego argumentu),

-        (chyba najciekawsze) ma działanie odwrotne – odejmowanie.

Istnienie działania odwrotnego, jak też już kiedyś mówiliśmy, można inaczej wyrazić, mówiąc, że każdy element ma element odwrotny względem tego działania (w dodawaniu mówi się zwykle przeciwny), tzn. dla każdego x (z rozpatrywanego zbioru – u nas Zn) istnieje (w rozpatrywanym zbiorze – u nas Zn) takie y, że wynik działania na x i y jest jego elementem neutralnym. U nas oznacza to, że dla każdego xÎZn istnieje takie yÎZn, że x+y=0 (mod n). Takim y jest, co łatwo sprawdzić, n-x. Ponieważ jest to element przeciwny do x, oznacza się go, jak w zwykłym dodawaniu, -x, czyli np. -5=3 (mod 8), -1=1 (mod 2), -3=3 (mod 6), -2=5 (mod 7), -0=0 (mod cokolwiek).

Dociekliwi zauważą może, że wyprowadzony wyżej wzór na różnicę modulo n daje się odczytać tak samo, jak inna definicja również zwykłego odejmowania: skoro b-a=b+(n-a), to odjąć liczbę znaczy dodać liczbę przeciwną! J

Drobna uwaga: zbiór, w którym zdefiniowane jest działanie spełniające te właśnie warunki, matematycy nazywają grupą przemienną. Można zatem zaszpanować stwierdzeniem: Zn z dodawaniem modulo n jest dla każdego n grupą przemienną.

§  Z mnożeniem jak zwykle gorzej, ale też na szczęście jest łączne i przemienne (dowody pozwolę sobie pominąć) i też ma element neutralny – jedynkę, za to nie w każdym Zn do każdego elementu q istnieje odwrotny – tym razem względem mnożenia, czyli rozwiązanie równania q×x=1 (mod n), co nazywane jest po prostu odwrotnością q i oznaczane q-1. Nie ma odwrotności oczywiście zero, ale tym się nie będziemy przejmować, tylko że – jak Was, mam nadzieję, przekonałem powyżej – czasem również dla innych q iloraz 1:q może nie mieć sensu (np. dla qÎ{2,3,4} w Z6). Ponieważ, jak napisałem, ma dla wszystkich q sens w Zn dla n będących liczbami pierwszymi (poza oczywiście q=0), możemy powiedzieć, że Zn\{0} z mnożeniem modulo n jest grupą (zawsze przy okazji przemienną) wtedy i tylko wtedy, gdy n jest liczbą pierwszą.

W pozostałych Zn (kiedy n jest liczbą złożoną) odwrotności mają elementy względnie pierwsze z n (tj. takie, że ich jedynym wspólnym dzielnikiem z n jest 1) – np. w Z6 są to liczby 1 i 5 (a ich odwrotności odnajdziemy z tabelki mnożenia modulo 6, szukając w wierszach 1 i 5 jedynek).

Mamy więc: 5-1=5 (mod 6), co można sobie też sprawdzić, wymnażając – faktycznie 5×5=1 (mod 6), czyli jest to liczbą, która jest w Z6 swoją własną odwrotnością!

1-1=1 (mod cokolwiek), bo 1×1=1 w każdym Zn – na tym polega jedynka! J

Z tabliczki mnożenia mod 5 odczytujemy: 2-1=3 (mod 5), 3-1=2 (mod 5) (tak jest zresztą zawsze, tj. a-1=b (mod n) Þ b-1=a (mod n) dla każdego n – a dlaczego?) oraz 4-1=4 (mod 5) (tak też zresztą jest zawsze, tj. n-1 ma odwrotność mod n dla każdego n i jest nią n-1, co zobaczyliśmy już parę linijek wyżej na przykładzie n=6).

I jeszcze kilka przykładów: 2005-1=2005 (mod 2006), 3-1=3 (mod 8) (czyli również inne liczby, poza 1 i n-1, mogą być swoimi własnymi odwrotnościami), 3-1=5 (mod 7), 2-1=4 (mod 7), ale 2-1 nie istnieje w Z10 (ani żadnym Z2k zresztą) – nie ma liczby, która pomnożona przez 2 da resztę 1 z dzielenia przez 10, podobnie nie istnieje 4-1 w żadnym Z2k ani 6-1 w Z9, a 0-1 nie istnieje w żadnym Zn!

Zbiór elementów mających odwrotności (czyli krótko: odwracalnych) w Zn matematycy oznaczają zwykle przez Zn*.

Zatem Zn* = Zn\{0} Û n jest liczbą pierwszą, czyli Z5*={1,2,3,4}, a np. Z6*={1,5} (ogólnie, jak już napisałem, Zn*={qÎZn: NWD(q,n)=1}).

Zauważmy też, że dla n będących liczbami pierwszymi Zn* z mnożeniem modulo n jest grupą przemienną (działanie jest łączne i przemienne, ma element neutralny i do każdego elementu istnieje odwrotność, dodatkowo jest to w ogóle działanie w tym zbiorze, tzn. iloczyn modulo n każdych dwóch jego elementów też do niego należy – wcześniej było to oczywiste, bo poruszaliśmy się po zbiorze wszystkich reszt z dzielenia przez n, a teraz odrzuciliśmy zero, no, ale właśnie zero nie jest iloczynem żadnych dwóch elementów Zn* (chociaż np. 2×5=0 (mod 10), ale 2 ani 5 nie są właśnie w Z10 odwracalne, czyli nie należą do Z10*)). Mówi się też, że Zn z dodawaniem i mnożeniem modulo n jest dla tych n ciałem. (Jest to bardziej złożona struktura algebraiczna niż grupa; jej najprostszymi może przykładami są właśnie zbiory Zn z działaniami mod n dla n będących liczbami pierwszymi).