kongruencje kasia: Jeżeli mam kongruencję x≡14 (mod 26) to czy mogę to rozpisać na układ x≡14 (mod 2) ⋀ x≡14 (mod 13). Jeżeli tak, to w jakim przypadku nie mogę tego zrobić, gdy zamiast 2 i 13 miałabym liczby, które nie są względnie pierwsze?

kasia: Będę wdzięczna, jeśli ktoś mi podpowie, czy to dobre rozumowanie.

b.: x≡14 (mod 26) oznacza, że 26 dzieli x−14 (oznaczenie: 26|x−14). Ponieważ 26=2*13 i 2,13 są względnie pierwsze, więc x≡14 (mod 26) <=> 26|x−14 <=> ( 2|x−14 oraz 13|x−14) <=> x≡14 (mod 2) ⋀ x≡14 (mod 13) Jeśli miałabyś N=ab, gdzie a, b nie są względnie pierwsze, to z N|x wynika, że a|x oraz b|x, ale nie na odwrót. Czyli jeśli miałabyś np. x≡14 (mod N), to stąd wynika, że x≡14 (mod a) ⋀ x≡14 (mod b), ale na odwrót już nie. Inaczej mówiąc, jeśli zamiast rozwiązywać x≡14 (mod N) będziesz rozwiązywać układ x≡14 (mod a) ⋀ x≡14 (mod b) to możesz dostać fałszywe rozwiązania −− musisz więc na koniec sprawdzić, które z rozwiązań układu spełniają wyjściową kongruencję.

Adamm: Tak. Jeśli masz jakieś równanie f(x) ≡ 0 (mod n₁n₂n₃...n_k) przy czym n₁, ..., n_k są względnie pierwsze, to równanie jest równoważne f(x) ≡ 0 (mod n_i) dla każdego i Jest to znane jako tzw. chińskie twierdzenie o resztach.