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 XV. 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,

spełniające w zbiorze liczb całkowitych zależność

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ę określoną dla wszystkich liczb całkowitych x,y Î Z następująco:

Czytamy: x przystaje do y modulo p wtedy i tylko wtedy, gdy p jest dzielnikiem różnicy x-y. Relacja przystawania modulo jest przykładem relacji równoważności. Łatwo sprawdzić, że dla dowolnych x ,y Î Z,

Zwrotność i symetria są oczywiste. Rozważmy przechodniość. Jeśli x przystaje do y modulo p oraz y przystaje do z modulo p, to na mocy definicji przystawania, x - y = k'p oraz y - z = k"p, dla pewnych liczb całkowitych k', k". Dodając stronami te równości otrzymamy  x - z = (k'+k")p. Zatem x przystaje do z modulo p.

Relację przystawania można zdefiniować nieco inaczej, jak przedstawiono w następującym lemacie 5.5.1.

Przykłady relacji równoważności opartych o zależność przedstawioną w lemacie 5.5.1 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:

ponieważ każda liczba całkowita przy dzieleniu przez p daje jedną (i tylko jedną) z możliwych reszt : 0, 1,..., (p-1).

Pytanie 5.5.1: 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)?

Zauważmy, że jeśli weźmiemy dwie liczby x, y postaci pk + i oraz pk' + j, dające przy dzieleniu przez p, odpowiednio 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 5.5.2.

Pytanie 5.5.2: Ile wynosi iloraz i reszta z dzielenia całkowitego (-3)* 7 przez 9?

Lemat 5.5.2 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,

określiliśmy dwie dwuargumentowe Å, Ä w zbiorze klas abstrakcji relacji º (mod p). Tabelki działań w przypadku, gdy p=3 przedstawiamy poniżej:

Łatwo można udowodnić, ż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 5.5.1

Wypisać tabelkę działań Å, Ä w przypadku, gdy p=7.