Zielony Smok

Kongruencje – definicja i działania matematyczne

Zestaw klas (Java) do pracy z konguencjami.

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