Kongruencje Olek: Muszę znaleźć wszystkie liczby całkowite x, dla których:

⎧	2x≡1(mod7)
⎨	3x≡99(mod192)
⎩	x≡25(mod98)

I mam pytanie, nie mogę tu zastosować Chińskiego twierdzenia o resztach, bo 192 i 98 nie są względnie pierwsze, czyli nie mogę rozwiązać tego układu?

Adamm: 2x = 1 (mod 7) ⇔ x = 4 (mod 7) x = 33 (mod 64) x = 25 (mod 98)

Adamm: w dodatku, 7|98, a 25 = 4 (mod 7), więc pierwsze równanie jest niepotrzebne

Olek: Nie rozumiem tylko, dlaczego to nie jest układ sprzeczny, skoro 7,192,98 nie są parami względnie pierwsze?

Adamm: a co to ma do rzeczy?

Olek: Nie wiem, że układ nie ma rozwiązań?Zbytnio nie pamiętam o co chodzi, ale mam w notatkach, że zawsze mam sprawdzić czy te liczby są względnie pierwsze.

Adamm: bzdury

Olek: I że to jest Chińskie twierdzenie o resztach

Adamm: W Chińskim twierdzeniu o resztach masz założenie że są względnie pierwsze. Co to ma do czegokolwiek.

Olek: No nie wiem, że jak mam układ np.

⎧	x≡ a1(mod m1)
⎩	x≡ a2(mod m2)

jeśli m₁ i m₂ są względnie pierwsze to dla dowolnych a₁,a₂ to układ jest niesprzeczny. Ma on dokładnie jedno rozwiązanie x₀ będące resztą modulo m₁m₂. Każde inne rozwiązanie różni się od x₀ o pewną wielokrotność iloczynu m₁m₂ Powyższy układ oznacza, ze reszta z dzielenia x/m₁ jest dokładnie taka jak reszta z dzielenia a₁/m₁ analogicznie drugi układ kongruencji. Czyli ten układ to poszukiwanie wszystkich liczb, które przy dzieleniu przez dwa zadane moduły dają z góry zadane reszty. Tak mam zapisane w zeszycie.

Adamm: no i po co mi go przepisywałeś?

Adamm: uważasz że ja nie wiem co to jest Chińskie twierdzenie o resztach?

Adamm: Nie, chodziło o Twój argument. Nie wiadomo o co Ci chodzi. Dlaczego niby równanie miałoby być sprzeczne?

Olek: Bo twierdzenie tak mówi?

Adamm: Gdzie tak mówi?

Adamm: Niczego takiego w twierdzeniu nie ma.

Olek: jeśli m1 i m2 są względnie pierwsze to dla dowolnych a1,a2 to układ jest niesprzeczny.

Adamm: no i dlaczego z tego miałoby wynikać że układ jest sprzeczny w przeciwnym wypadku?

Olek: Po prostu jeżeli to nie ma znaczenia dla układu równań, to po co jest to założenie w twierdzeniu?

Adamm: twierdzenie to jedno, a zadanie to jedno

Olek: To nie muszę go stosować, zawsze kiedy mam układ kongruencji? Ale przecież tobie nie wyszedł jednoznacznie wyznaczony x, ani też jego wielokrotności

Adamm: bo nie rozwiązałem zadania, tylko je uprościłem w tej postaci w jakiej jest teraz, można zastosować Chińskie twierdzenie o resztach

Adamm: musisz zawsze stosować tak Ci mówi Pan Stasiu z pod sklepiku

Adamm: oczywiście że nie musisz, pomyśl trochę twierdzenia są po to żeby Ci ułatwić sprawę, a nie po to żeby ich je powtarzać jak mantrę

Mila: x = 33 (mod 64) x = 25 (mod 98)⇔ −−−−−−−−−−−−−−−−− x=64k+33, k∊C x=98m+25 , m∊C −−−−−−−−−−−−−−−−−−− 98m+25=64k+33 98 m=64k+8 /:2 49m=32k+4 ⇔ 32m+17m=32k+4 17m=32k+4 /*17 289m=32*17k+68 288m+1m=32k+68 m=32k+68 −−−−−−−−− x=98*(32k+68) x=3136k+6664+25 x=3136k+3136*2+392+25 x=3136k+417 ========= sprawdzenie: x=417 1) 2*417=834=119*7+1⇔2*417≡1 (mod7) 2) 3*417=1251=6*192+99⇔3*417≡99 (mod192) 3) 417=4*98+25 ===============

Mariuszek: 2x = 1 (mod 7) ⇔ x = 4 (mod 7) x = 33 (mod 64) x = 25 (mod 98) x = 4 (mod 7) x = 33 (mod 64) x = 25 (mod 98) Można użyć chińskiego twierdzenia o resztach choć nie bezpośrednio Jak Adam zauważył pierwsze równanie jest niepotrzebne x = 33 (mod 64) x = 25 (mod 98) Teraz drugie równanie można rozbić na x = 1 (mod 2) x = 25(mod 49) Zatem mamy x = 33 (mod 64) x = 1 (mod 2) x = 25(mod 49) I tutaj występuje podobna sytuacja o której pisał Adam Zostaje nam układ równań x = 33 (mod 64) x = 25(mod 49) i teraz można użyć chińskiego twierdzenia o resztach 64=1*49+15 , 15=1*64−1*49 49=3*15+4 , 4=1*49−3*15 15=4*3+3 , 3=1*15−3*4 4=1*3+1 , 1=1*4−1*3 1=1*4−1*(1*15−3*4) 1=4*4−1*15 1=4*(1*49−3*15)−1*15 1=4*49−13*15 1=4*49−13*(1*64−1*49) 1=17*49−13*64 x = 33 (mod 64) x = 25(mod 49) x = (17*49*33−13*64*25)mod 3136 17*33=25²−8²=625−64=561 561*(50−1)=28050−561=27489 13*64*25=13*16*100=20800 x = (27489−20800) (mod 3136) x=6689 mod 3136 6689−6272=417 x=417 (mod 3136) czyli jednak wychodzi z chińskiego twierdzenia o resztach co