« poprzedni punkt | następny punkt » |
Pewne relacje równoważności mają dodatkowo własność, że jeśli wykonuje się operacje na elementach równoważnych, to wyniki tych operacji są też równoważne. Takie relacje równoważności nazywa się kongruencjami. Najprostszym przykładem kongruencji jest relacja równości. Dokładniej o kongruencjach w dowolnych systemach algebraicznych będziemy mówili w wykładzie 10. Teraz poznamy pewne szczególne przykłady kongruencji.
Niech p > 0 i x mod p oznacza, jak zwykle, resztę, a x div p oznacza iloraz otrzymany z dzielenia całkowitego x przez p (tzn. x div p jest największą liczbą całkowitą mniejszą lub równą x/p, czyli x div p = ë x/pû ). Mamy więc dwie operacje dwuargumentowe mod i div,
mod : Z ´ N>0 ® N>0 , div : Z ´ N>0 ® Z
spełniające w zbiorze liczb całkowitych zależność
p * (x div p) + x mod p = x. (*)
Zwróćmy uwagę, że reszta z dzielenia przez p jest liczbą naturalną mniejszą niż p. Zatem 5 mod 3 = 2, a (-5) mod 3 = 1, bo 3*(-2) +1 = -5.
Rozważmy relację równoważności określoną dla wszystkich liczb całkowitych x,yÎ Z następująco:
x º y (mod p) wttw x mod p = y mod p.
Czytamy: x przystaje do y modulo p wtedy i tylko wtedy, gdy reszty z dzielenia przez p liczb x i y są takie same. Relację º nazywamy relacją kongruencji modulo p. Relacja przystawania jest przykładem relacji równoważności. Łatwo sprawdzić, że dla dowolnych x ,yÎ Z,
x º x (mod p)
jeśli x º y (mod p), to y º x (mod p)
Jeśli x º y (mod p) i y º z (mod p), to x º z (mod p).
Własności zwrotności, symetrii i przechodniości są konsekwencją tych właśnie cech przysługujących relacji równości, użytej w definicji przystawania.
Lemat 4.3
Dla dowolnego pÎ Z, p>0 i dla dowolnych x,yÎ Z,
x º y (mod p) wtedy i tylko wtedy, gdy (x-y) jest wielokrotnością p.
Dowód.
Niech x div p = k, y div p = k'. Z wzoru (*) mamy (x-kp) = x mod p i (y-k'p) = y mod p. Jeśli x przystaje do y modulo p, to na mocy definicji przystawania, (x-kp) = (y-k'p), a zatem różnica x-y jest podzielna przez p ( bo x-y = kp - k'p). Odwrotnie, jeśli x-y = kp, to x = kp + y, więc reszta z dzielenia x przez p musi być taka sama jak reszta z dzielenia y przez p (bo człon kp jest podzielny przez p).
Przykłady relacji równoważności opartych o zależność przedstawioną w lemacie 4.3 już spotkaliśmy wcześniej. W przypadku ogólnym, gdy p jest dowolnie ustaloną liczbą całkowitą dodatnią, relacja przystawania modulo p wyznacza p klas abstrakcji:
[0] = {pk +0 : kÎ Z}, [1] = {pk+1 : kÎ Z}, ... , [p-1] = {pk + (p-1) : kÎ Z},
ponieważ każda liczba całkowita przy dzieleniu przez p daje jedną (i tylko jedną) z możliwych reszt : 0, 1,..., (p-1).
Pytanie 8: Weźmy p = 7 i dowolne dwie liczby x, y należące do klas [4] oraz [1]. Do jakiej klasy należy ich suma (x+y)?
Zobacz odpowiedźZauważmy, że jeśli weźmiemy dwie liczby x, y postaci pk + i oraz pk' + j, dające przy dzieleniu przez p, reszty i oraz j, to ich suma p*(k+k') + (i+j) daje przy dzieleniu przez p taką samą resztę jak (i+j) przy dzieleniu przez p. Analogicznie, iloczyn tych liczb x*y = (pk + i)*(pk' + j) = p(pkk'+ kj + k'i) + ij. Zatem reszta z dzielenia iloczynu x*y jest taka sama jak reszta z dzielenia i*j przez p. Wynika stąd, że działając niezależnie na różnych elementach dwóch ustalonych klas, zawsze trafiamy do tej samej klasy abstrakcji ze względu na relację przystawania modulo p. Obserwacja ta stanowi treść lematu 4.4.
Lemat 4.4
Dla dowolnych liczb całkowitych x, y, x', y' Î Z oraz dla dowolnego pÎ N>0, jeśli x º y(mod p) oraz x' º y'(mod p), to (x+y) º (x'+y')(mod p) oraz (x*y) º (x'*y')(mod p).
Pytanie 9: Ile wynosi iloraz i reszta z dzielenia całkowitego (-3)* 7 przez 9?
Lemat 4.4 sugeruje, że możemy wprowadzić pewne operacje odpowiadające zwykłym operacjom arytmetycznym na klasach abstrakcji relacji kongruencji modulo p. Rzeczywiście, przyjmując dla dowolnych liczb całkowitych x, y,
[x] Å [y] =df [x+y]
[x] Ä [y] = df [x*y]
określiliśmy dwie dwuargumentowe Å , Ä w zbiorze klas abstrakcji relacji º (mod p). Tabelki działań w przypadku, gdy p=3 przedstawiamy poniżej:
Å |
[0] |
[1] |
[2] |
[0] |
[0] |
[1] |
[2] |
[1] |
[1] |
[2] |
[0] |
[2] |
[2] |
[0] |
[1] |
Ä |
[0] |
[1] |
[2] |
[0] |
[0] |
[0] |
[0] |
[1] |
[0] |
[1] |
[2] |
[2] |
[0] |
[2] |
[1] |
Łatwo można sprawdzić, że operacje Å , Ä mają własności podobne do własności dodawania i mnożenia w zbiorze liczb całkowitych: są przemienne i łączne. Sprawdzenie tego faktu pozostawiamy Czytelnikowi.
Zadanie 4
Wypisać tabelkę działań Å, Ä w przypadku, gdy p=7.
« poprzedni punkt | następny punkt » |