Wykład 7

Kongruencje

7.1

Relacja przystawania modulo m

Definicja 7.1. Niech m ∈ N. Wprowadźmy w zbiorze liczb całkowitych relację kongru-

encji (przystawania) liczb modulo m, oznaczaną symbolem „ ≡ (mod m)”, następują-

co:

∀

a, b∈Z

a ≡ b (mod m) ⇐⇒ (a MOD m) = (b MOD m).

Twierdzenie 7.1. Relacja przystawania modulo m jest relacją równoważności. Klasy

abstrakcji tej relacji są reprezentowane jednoznacznie przez elementy zbioru Z

m

.

Twierdzenie 7.2. Niech m, n będą dowolnymi liczbami naturalnymi oraz a, b, c, d —

dowolnymi liczbami całkowitymi. Wówczas

(a) Jeżeli a ≡ b (mod m) i c ≡ d (mod m), to a + c ≡ b + d (mod m) i ac ≡ bd

(mod m).

(b) Jeżeli a ≡ b (mod m) oraz d|m i d ∈ N, to a ≡ b (mod d).

(c) Jeżeli a ≡ b (mod m), a ≡ b (mod n) i NWD(m, n) = 1, to a ≡ b (mod mn).

7.2

Kongruencje liniowe

Zadanie: Dla danych liczb całkowitych a, b oraz liczby naturalnej m znaleźć wszystkie

liczby całkowite x, dla których zachodzi

ax ≡ b (mod m).

(7.1)

Zadanie takie będziemy nazywać liniowym równaniem kongruencyjnym lub, krótko, kon-

gruencją liniową.

22

Uwaga 7.1. Dla dowolnych liczb a, b ∈ Z oznaczmy a

0

= a MOD m i b

0

= b MOD m.

Wówczas kongruencja

ax ≡ b (mod m)

ma taki sam zbiór rozwiązań, jak kongruencja

a

0

x ≡ b

0

(mod m).

(7.2)

Uwaga 7.2. Jeżeli a

0

= 0 (czyli: a ≡ 0 (mod m)), to kongruencja (7.2) ma rozwiązanie

wtedy i tylko wtedy, gdy również b

0

= 0 i wówczas rozwiązaniem jest każda liczba

całkowita.

Uwaga 7.3. Jeżeli m = 1, to rozwiązaniem kongruencji (7.2) jest każda liczba całkowita.

Uwaga 7.4. Poszukiwanie rozwiązania kongruencji (7.2) w zbiorze Z

m

jest równoważne

szukaniu rozwiązań równania a

0

·

m

x = b

0

w pierścieniu Z

m

.

Twierdzenie 7.3. Niech m ∈ N i a ∈ Z

+
m

, b ∈ Z

m

będą dowolnymi liczbami. Wówczas:

1

0

. Jeżeli NWD(a, m) = 1, to istnieje dokładnie jedno rozwiązanie x

0

∈ Z

m

kongruencji

(7.1). Każde inne rozwiązanie x tej kongruencji ma postać

x = x

0

+ km

dla pewnego k ∈ Z.

2

0

. Jeżeli NWD(a, m) = d > 1, to rozwiązanie kongruencji (7.1) istnieje wtedy i tylko

wtedy, gdy d|b. Jeżeli d|b, to kongruencja (7.1) jest równoważna kongruencji

a

′

x ≡ b

′

(mod m

′

),

(7.3)

gdzie a

′

= a/d, b

′

= b/d oraz m

′

= m/d.

7.3

Układy kongruencji

Twierdzenie 7.4 (Chińskie twierdzenie o resztach). Niech m

1

, m

2

, . . . , m

k

∈ N

będą liczbami parami względnie pierwszymi i m = m

1

m

2

·. . .·m

k

. Wówczas dla dowolnych

liczb całkowitych a

1

, a

2

, . . . , a

k

układ kongruencji











































x ≡ a

1

(mod m

1

),

x ≡ a

2

(mod m

2

),

· · ·

· · ·

x ≡ a

k

(mod m

k

)

(7.4)

ma dokładnie jedno rozwiązanie x

0

∈ Z

m

. Każde inne rozwiązanie x układu (7.4) ma

postać x = x

0

+ lm dla pewnego l ∈ Z.

23