9467141765

(2)    Jeśli a = 6 (modm), to b = a (modm) (symetria relacji =).

(3)    Jeśli a = b (modm) i b = c (modm), to a = c (modm) (przechodniość relacji =).

(4)    Jeśli a = b (modm), to (a — b) = 0 (modm).

(5)    Jeśli a = b (modm) i c = d (modm), to a + c = (b + d) (modm).

(6)    Jeśli a = b (modm) i c = d (modm), to a c = (b d) (modm).

(7)    Jeśli Oj = bi (modm), (dj, b_t € Z, i e {1,2,k}), to J2^ai = (modm).

(8)    Jeśli a = b (modm), to a^k = b^k (modm), (k G N).

(9)    Jeśli a = b (modm) i d > 0 i d | m, to a = b (modd).

(10)    Jeśli a = b (modm) i c > 0, to ac = 6c(modmc).

(11)    Jeśli ca = cft(modm) i (c, m) = 1, to a = 6 (modm).

Twierdzenie. Niech / oznacza wielomian o współczynnikach całkowitych. Wówczas, jeśli a = b (modm), to f (a) = f (b) (modm).

Przykład. (Cecha podzielności przez 11). Liczba naturalna a dzieli się przez 11 wtedy i tylko wtedy, gdy różnica pomiędzy sumą jej cyfr znajdujących się na miejscach nieparzystych, a sumą jej cyfr znajdujących się na miejscach parzystych jest podzielna przez 11.

Rozwiązanie

Niech liczba a w rozwinięciu dziesiętnym ma postać a — a_n (10)" + a_n_i (10)"^-1 +

... + ailO + eto- Zauważmy dalej, że 10 = —1 (modli). Wobec powyższego twierdzenia / (10) = / (—1) (modli), gdzie / jest wielomianem postaci a_nxⁿ-(-a„_ix"^-1 + ...-|-aia;+ao. Zatem

a = a_n (10)"+a_n_i (10)^n-1+...+ailO+ao = On (—l)ⁿ+a„_i (—l)"^-1+...+ai (—l)+ao (modli).

Twierdzenie. (Chińskie twierdzenie o resztach). Niech mi,m2,...,m„ (n > 1), będą liczbami naturalnymi parami względnie pierwszymi, tzn (m,i,mj) = 1 dla i j (i,j €

{1,2, ...,n}) i niech ri,r2,..., r_n będą dowolnymi liczbami całkowitymi. Wówczas istnieje wspólne rozwiązanie układu kongruencji

x = ri (modmi),

^    x = r₂ (modm₂),

x = r_n (modm_n).

Rozwiązanie, to jest jedyne modulo m—m\ m₂ ... m„.

Czyli, jeśli xq jest pewnym rozwiązaniem układu (*), to liczba całkowita x jest rozwiązaniem układu (*) wtedy i tylko wtedy gdy jest postaci x = xq + km, gdzie m = m\ m₂ ...m_n, k e Z.