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?
23 lis 19:32
kasia: Będę wdzięczna, jeśli ktoś mi podpowie, czy to dobre rozumowanie.
23 lis 21:23
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ę.
24 lis 05:34
Adamm: Tak. Jeśli masz jakieś równanie f(x) ≡ 0 (mod n1n2n3...nk) przy czym n1, ..., nk są względnie pierwsze, to równanie jest równoważne f(x) ≡ 0 (mod ni) dla każdego i Jest to znane jako tzw. chińskie twierdzenie o resztach.
24 lis 12:28