276062002

1.5. Kongruencje i ich własności, twierdzenie chińskie o resztach 11

Przejdziemy teraz do rozważania równań oraz układów równań kongruencyjnych. Łatwo sprawdzić kiedy jedno równanie postaci ax = 6(mod m) posiada rozwiązanie całkowite - warunkiem koniecznym i wystarczającym na podstawie tożsamości Bezouta jest, aby NWD(a,m)|6.

Własność 1.5.5 (rozwiązanie kongruencji liniowej). Niecka, b G Z, m G N. Wtedy istnieje rozwiązanie kongruencji ax = b(mod m) wtedy i tylko wtedy, gdy NWD(a,m)\b.

Dowód. Zauważmy, że istnienie rozwiązania naszej kongruencji jest równoważne temu, że istnieje x G Z takie, że m\ax — b co z kolei jest równoważne stwierdzeniu, iż istnieje y G Z takie, że ax — b = my czyli ax — my = b.

Jeśli więc NWD(a,ra) nie dzieli b to lewa strona jest podzielna przez d zaś prawa nie, więc nie może istnieć rozwiązanie naszej kongruncji.

Z drugiej strony jeśli b = cd to wystarczy zastosować identyczność Bezouta i znaleźć a, (3 G Z takie, że d = aa + (im. Domnażając obie strony przez c dostajemy równość: b = caa + c(3m, czyli x — ca jest rozwiązaniem naszej kongruencji.    □

Interesować nas będzie teraz poszukiwanie rozwiązania układów równań kongruencyjnych, (liniowych). Podstawowym tutaj twierdzeniem jest wspomniane w tytule chińskie twierdzenie o resztach.

Twierdzenie 1.5.6 (chińskie o resztach, TCR). C.5 Z: m\,..., m_r G N - parami względnie pierwsze, k\,..., k_r G Z.

T: (1) Istnieje l G Z takie, że l = ki(mod m,) dla każdego i = 1,... ,r.

(2) Jeśli l, l' spełniają (1), to 1 = l'(mod m) gdzie m = m\ -... - m_r.

Dowód. Niech m := m\ ■... ■ m_r oraz s, := ^l. Wtedy s* jest iloczynem liczb mj dla j ^ i wobec tego jest iloczynem liczb względnie pierwszych z mj. Z 1.5.4(4) wynika, że również rrij i Si są względnie pierwsze. Wobec tego istnieją aj,..., a_r, b\,..., b_r G Z takie, że

aimi + b{Si = 1 dla i = 1,..., r.

Określmy teraz lk\(b\S\) + ... + k_r(b_rs_r). Wykażemy, że takie właśnie l spełnia warunki tezy.

Ustalmy i₀ G {1,..., r}. Wtedy

l-k_io = h(bisi) + ... + k_io(b_ios_io - 1) + ... + k_r(b_rs_r).

Ale mi₀\ai₀mi₀ = 1 — 6j₀s,₀ oraz s, dla z ^ żo są podzielne przez mj₀ czyli l = ki_Q(mod mj₀), czego oczekiwaliśmy.

Niech teraz l' spełnia również tę kongruencję, to oznacza, że l' — l jest podzielne przez każde mj. Wobec tego z 1.5.4(5) wynika, żel' — l jest podzielne przez iloczyn mi ■... • m_r i mamy tezę.    □

Zauważmy przy okazji, że dowód twierdzenia chińskiego o resztach dostarcza nam konkretnego algorytmu znajdowania rozwiązania układu kongruencji.