Kongruencja

Kongruencja to relacja, która dzieli zbiór na klasy abstrakcji o tej samej reszcie przy dzieleniu przez określoną liczbę. Kongruencja określona jest w zbiorze liczb całkowitych i nazywana jest też przystawaniem liczb modulo n.

Liczby całkowite a i b przystają modulo n, co zapisujemy: a ≡ b (mod n), jeżeli ich różnica a - b dzieli się bez reszty przez n. Równoważnie: jeśli liczby a i b dają w dzieleniu przez n taką samą resztę.

Kongruencje o tym samym module można dodawać, odejmować lub mnożyć stronami. Można przenosić wyrazy z jednej strony kongruencji na drugą, zmieniając ich znaki. Obie strony kongruencji można podnosić do tej samej potęgi (o naturalnym wykładniku). Nie można natomiast dzielić stronami kongruencji.

Własności kongruencji

- zwrotność: dla dowolnej liczby całkowitej a: a ≡ a (mod n).

- symetryczność: jeżeli dla liczb całkowitych a i b: a ≡ b (mod n), to: b ≡ a (mod n).

- przechodniość: jeśli dla liczb całkowitych a, b i c:
a ≡ b (mod n) i b ≡ c (mod n), to: a ≡ c (mod n).

- kongruencja sumy: jeżeli a ≡ p (mod n) i b ≡ q (mod n), to (a+b) ≡ (p+q) (mod n)

- kongruencja iloczynu: jeżeli a ≡ p (mod n) i b ≡ q (mod n), to a · b ≡ p · q (mod n)