Kongruencje – definicja i działania matematyczne
Kongruencja nazywana jest też przystawaniem liczb.
Definicja
Mówimy, że zachodzi kongruencja
(czytaj: a przystaje do b modulo m) jeżeli
jest podzielne przez 
, co oznacza, że:
jest wielokrotnością .
Relacja równoważności ≡ jest zwrotna, symetryczna i przechodnia.
Sprawdzenie:
gdyż 
jest podzielne przez 
.
Zwróćmy uwagę, że (mod oznacza tutaj operator zwracający resztę z dzielenia):
a mod m = b mod m
Sprawdzenie:
1783 mod 5 = 3 oraz
98 mod 5 = 3
Działania na kongruencjach
Dodawanie stronami
Jeżeli zachodzą kongruencje:
oraz
to zachodzi również
.
Sprawdzenie:
Jeżeli
12≡7(mod 5) i
27≡42(mod 5) to
12+27≡7+42(mod 5) czyli
39≡49(mod 5)
Odejmowanie stronami
Jeżeli zachodzą kongruencje:
oraz
to zachodzi również
Sprawdzenie:
Jeżeli
15≡6(mod 9) oraz
12≡21(mod 9) to
15-12≡6-21(mod 9) czyli
3≡-15(mod 9)
Mnożenie stronami
Jeżeli zachodzą kongruencje:
oraz
to zachodzi również
Sprawdzenie:
Jeżeli
15≡8(mod 7) oraz
3≡10(mod 7) to
15⋅3≡8⋅10(mod 7), czyli
45≡80(mod 7)
Mnożenie przez liczbę
Jeżeli zachodzi kongruencja:
to zachodzi również:
Sprawdzenie:
Jeżeli
5≡2(mod 3) to
5⋅4≡2⋅4(mod 3), czyli
20≡8(mod 3)
Potęgowanie stronami
Jeżeli zachodzi kongruencja:
to zachodzi również
pod warunkiem, że
Sprawdzenie:
Jeżeli
5≡2(mod 3) to również zachodzi
54≡24(mod 3), czyli
625≡16(mod 3)
Dzielenie przez wspólny dzielnik
Dzielenie kongruencji jest możliwe tylko w szczególnych przypadkach.
Jeżeli zachodzi kongruencja:
to zachodzi również
pod warunkiem, że liczba d dzieli liczby a, b i m.
Sprawdzenie:
Jeżeli
15≡6(mod 9), więc
(15:3)≡(6:3)(mod (9:3)), czyli
5≡2(mod 3), gdyż
liczba 3 dzieli 15, 6 i 9.
Niektóre właściwości
Najmniejsza wspólna wielokrotność (nww)
Jeżeli
a ≡ b (mod m1) oraz
a ≡ b (mod m2) to
a ≡ b (mod nww(m1, m2))