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))

Więcej informacji

Jak w języku Java działa operator dzielenia z resztą %
Jak w języku Java przygotować operator kongruencji mod
Jak w języku Java przygotować metody wykonujące dodawanie, odejmowanie, mnożenie i potegowanie modularne
Klasa Java do operacji na kongruencjach
Na stronie Java z Arią znajdziesz też informacje o operatorze dzielenia z resztą (remainder) oraz operatorze kongruencji (mod) w klasie BigInteger w języku Java.