Układ kongruencji Przemysław: Proszę o rozwiązanie:

⎧	4x+6≡3 (mod 5)
⎜
⎨	3x−5≡4 (mod 5)
⎜
⎩	5x+4≡10 (mod 11)

bo po sprowadzeniu do:

⎧	264x≡−198 (mod 330)
⎜
⎨	165x≡495 (mod 330)
⎜
⎩	150x≡180 (mod 330)

nie wiem jak sobie z tym poradzić

Przemysław: Dochodzę do 51x≡127 (mod 330) czyli 51x=330k+127 a to jest sprzeczne, czyli cały układ kongruencji jest sprzeczny, prawda?

Przemysław: Jak ktoś zajrzy to od razu kolejne pytanie: wychodzi mi, że układ:

⎧	x≡3 (mod 6)
⎜
⎨	x≡9 (mod 15)
⎜
⎩	x≡18 (mod 21)

też jest sprzeczne, czy to prawda?

jc: I równanie: 4x + 6 ≡ 3 (mod 5) ⇔ x ≡ 3 (mod 5) (mnożymy przez 4) II równanie: 3x − 5 ≡ 4 (mod 5) ⇔ x ≡ 3 (mod 5) (mnożymy przez 5) III równanie: 5x+4 ≡ 10 (mod 11) ⇔ x ≡ 10 (mod 11) (mnożymy przez 9) 43 ≡ 3 (mod 5) 43 ≡ 10 (mod 11) Rozwiązanie x ≡ 43 (mod 55) tzn x = 43 + 55*k

Przemysław: Hmm... To coś mocno namieszałem Dziękuję. A to drugie?

Mariusz: Chińskie twierdzenie o resztach miałeś ?

Przemysław: Tak, ale jeszcze muszę się nauczyć porządnie.

Mariusz: W tym drugim rozbij ten układ tak aby moduły były względnie pierwsze

Przemysław: Tak też robiłem. Więc wychodzi coś takiego:

⎧	x≡3 (mod 2)
⎜
⎜	x≡0 (mod 3)
⎨
⎜	x≡4 (mod 5)
⎜
⎩	x≡4 (mod 7)

prawda?

Mariusz: x≡3 mod 6 zamieniasz na x≡1 mod 2 x≡0 mod 3 x≡9 mod 15 zamieniasz na x≡0 mod 3 x≡4 mod 5 x≡18 mod 21 zamieniasz na x≡0 mod 3 x≡4 mod 7 oraz wyrzucasz z układu te które się powtarzają

Mariusz: Tak coś takiego

Mariusz: Chociaż tę pierwszą kongruencję można jeszcze uprościć

Przemysław: Potem sprowadziłem to do NWW modułów:

⎧	70x≡0 (210)
⎜	105x≡105(mod 210)
⎜
⎨	42≡168(mod 210)
⎜
⎩	30x≡120(mod 210)

1. z 3. dodałem stronami 2. z 4. dodałem stronami:

⎧	112x≡168(mod 210)
⎨
⎩	135x≡225(mod 210)

odjąłem stronami: 27x≡57 (mod 210) i teraz zostaje do rozwiązania: 27x=210k+57 27x−210k=57 podstawiam: x₁=x−6k x=x₁+6k 51x₁−24k=57 k₁=k−2x₁ k=k₁+2x₁ 51x₁−24k₁−48x₁=57 3x₁−24k₁=57 x₂=x₁−8k₁ x₁=x₂+8k₁ 3x₂=57 x₂=19 no faktycznie, nie wiedzieć czemu zamiast 57 wziąłem 127 i to się nie dzieliło

Przemysław: Jakieś bzdury napisałem w ogóle. Dobra, 20:25 jest nieważne

Przemysław: Co do 20:21 to wydaje mi się, że tak właśnie zrobiłem i to jest postać po wyrzuceniu powtarzających się (z uwzględnieniem, że 3≡1 mod 2)

jc: Mariusz, a to prezent (program w Pythonie ilustrujący Ch. Tw. o resztach dla n=3, ale łatwo uogólnić): −−−−−−−−−−−−−−−− def odwr(a,b): x=1 z=0 while b<>0: k=a/b a,b,x,z=b,a%b,z,x−k*z return x def nwd(a,b): while b<>0: a,b=b,a%b return a print "chinskie twerdzenie o resztach" print "wprowadz 3 liczby parami wzglednie pierwsze" m1,m2,m3=input("m1="),input("m2="),input("m3=") print "nwd (", m1,m2,") = ",nwd(m1,m2) print "nwd (", m1,m3,") = ",nwd(m1,m3) print "nwd (", m2,m3,") = ",nwd(m2,m3) print "wprowadz 3 reszty" r1,r2,r3=input("r1="),input("r2="),input("r3=") m=m1*m2*m3 n1=odwr(m2*m3,m1) n2=odwr(m1*m3,m2) n3=odwr(m1*m2,m3) n=(n1*m2*m3*r1+m1*n2*m3*r2+m1*m2*n3*r3)%m; print "reszta z dzielenia", n, "przez ", m1, " = ", n%m1 print "reszta z dzielenia", n, "przez ", m2, " = ", n%m2 print "reszta z dzielenia", n, "przez ", m3, " = ", n%m3

Mariusz: x≡1 mod 2 x≡0 mod 3 x≡4 mod 5 x≡4 mod 7 x≡1 mod 2 x≡0 mod 3 x≡4 mod 35 x≡1 mod 2 x≡0 mod 3 −1*2*0+1*3*1=3 x≡3 mod 6 x≡4 mod 35 6*6*4−1*35*3=144−105 x≡39 mod 210

Mariusz: Ja chyba takie coś w C kiedyś napisałem (dla statycznie alokowanej tablicy , jak w Pascalu)

jc: Mariusz To wersja ogólna, wynik jak u Ciebie = 39 def odwr(a,b): x=1 z=0 while b<>0: k=a/b a,b,x,z=b,a%b,z,x−k*z return x def nwd(a,b): while b<>0: a,b=b,a%b return a # dane wejsciowe k = 4 # liczba modulow m = [2,3,5,7] # moduly r = [1,0,4,4] # reszty mm = 1 for i in range(k): mm *= m[i] n= 0 for i in range(k): n += mm*odwr(mm/m[i], m[i])/m[i]*r[i] n %= mm print n

Przemysław: Dziękuję bardzo

Mariusz: #include<iostream> #include<cstdlib> #include<conio.h> using namespace std; inline void clrscr() {system("cls");}; typedef struct{ long a,b; }ratio; long gcdex(long,long,long*,long*); ratio chrem(ratio,ratio); int main(){ char ch; ratio x[50]; long i,n; clrscr(); do{ n=−1; while(!(n>0&&n<=50)){ cout<<"Podaj ilosc rownan<=50\n"; cin>>n; } for(i=0;i<=n−1;i++){ cout<<"Podaj a["<<i+1<<"]=(reszta dzielnik)\n"; cin>>x[i].a>>x[i].b; } for(i=0;i<n−1;i++) x[i+1]=chrem(x[i],x[i+1]); cout<<"Wynik to : "; cout<<x[n−1].a<<" modulo "<< x[n−1].b<<endl; cout<<endl; ch=getch(); } while(ch!=27); return 0; } long gcdex(long a,long b,long *x,long *y){ long quot; long a0=a,b0=b; long p=1,q=0,r=0,s=1; long c,new_r,new_s; while(b!=0){ c=a%b; quot=a/b; a=b; b=c; new_r=p−quot*r; new_s=q−quot*s; p=r; q=s; r=new_r; s=new_s; } if(a0*p+b0*q<0) (*x)=−p; else (*x)=p; if(a0*p+b0*q<0) (*y)=−q; else (*y)=q; return abs(a0*p+b0*q); } ratio chrem(ratio x,ratio y){ ratio z,lc; long c; c=gcdex(x.b,y.b,&lc.a,&lc.b); if(c==1){ z.b=abs(x.b*y.b); z.a=(x.b*lc.a*y.a+y.b*lc.b*x.a)%z.b; if(z.a<0) z.a=(z.b+z.a)%z.b; } return z; } W C++ ale łatwo przełożyć na Pascala w c/c++ można zastosować tablicę z dynamicznie allokowaną pamięcią

jc: Mariusz, czytając Twój program zauważyłem, że mój jest nadmiarowy wystarczy odwracać (Twoje gcdx), nigdzie nie używmam nwd. Przy okazji, Python ma arytmetykę dowolnego rozmiaru (chyba mówi sie inaczej, ale uciekło mi słowo). Wszystkim polecam, ale tylko 2 osoby przekonałem. def odwr(a,b): x=1 z=0 while b<>0: k=a/b a,b,x,z=b,a%b,z,x−k*z return x k = 4 # liczba modulow m = [2,3,5,7] # moduly r = [1,0,4,4] # reszty mm = 1 for i in range(k): mm *= m[i] n= 0 for i in range(k): n += mm*odwr(mm/m[i], m[i])/m[i]*r[i] n %= mm print n

Przemysław: Dobra, inną metodą doszedłem do rozwiązania: −4161, co się zgadza, o ile się nie mylę. Ale faktycznie lepiej jak nauczę się tego algorytmu z 20:54

jc: Mariusz, a to taka wygładzona wersja def odwr(a,b): x=1 z=0 while b<>0: k=a/b a,b,x,z=b,a%b,z,x−k*z return x d = [ [2,1],[3,0],[5,4],[7,4] ] # dane wejsciowe p = 1 for t in d: p *= t[0] n= 0 for t in d: n += p*odwr(p/t[0], t[0])/t[0]*t[1] print n%p

Mariusz: Zależy do czego python jest interpretowany i pliku exe nie zrobisz Zdaje się że można było zapisać do pliku z rozszerzeniem .py i ładować importem

Mariusz: Jako pierwszy język to chyba najlepszy jest Pascal Słówka kluczowe są w języku angielskim a nie jakieś klamerki Są moduły , biblioteki (dla trybu chronionego DOSa i Windowsa) Turbo Pascal ma także elementy programowania obiektowego (typ object)

Przemysław: Przepraszam jeszcze, gdybyście mi jeszcze powiedzieli jak szukać b=[(a)⁻¹]_m, że: b*a=1 mod m to byłoby super Bo można to wymyślać, ale wolałbym jakiś algorytm, a wiem, że można uogólnionym algorytmem Euklidesa, ale nie wiem jak.

jc: Rozszerzony Algorytm Euklidesa. 13, 5 13 = 2*5 + 3 5 = 1*3 + 2 3 = 1*2 + 1 1 = 3 − 2 = 3 − (5 − 3) = 2*3 − 5 = 2*(13 −2*5) − 5 = 2*13 − 5*5 Zatem (−5)*5 ≡ 1 (mod 13), lub inaczej 8*5 ≡ 1 (mod 13) (zły przykład, przecież od razu widać rozwiązanie) W programie liczymy nieco inaczej: każda kolejna reszta jest postaci x*13+y*5 (pomyśl dlaczego).

jc: Mariusz Tak, Python jest interpretowany. Oczywiście, że tekst wpisujemy do pliku (choć można pracować w trybie interakcyjnym). Dla mnie główną zaletą Pythona jest niezwykle czytelny tekst (żadnych klamerek, średników, dklaracji, są za to wcięcia).

Przemysław: Bardzo sprytnie Każda kolejna reszta z dzielenia przez ile? (w programy się nie zagłębiam, bo z moimi wybitnymi zdolnościami informatycznymi zrozumienie mogłoby trochę zająć).

Przemysław: W każdym razie dziękuję bardzo

jc: Nie czytaj dalej, jeśli nie znasz algorytmu Euklidesa. Od tego musisz zacząć 13 = 1*13 + 0*5 5 = 0*13 + 1*5 13 = 2*5 + 3, 3 = 1*13 − 2*5 5 = 1*3 + 2, 2 = 5−1*3 = 5 − 1*(1*13−2*5) = − 1*13 + 3*5 3 = 1*2 + 1, 1 = 3 − 1*2 = (1*13 − 2*5) − 1*(−1*13 +3*5) = 2*13 − 5*5 kolejne reszty to: 13, 5, 3, 2, 1 Ale lepiej zapisać to na symbolach ... Marisz, a czy znasz binarny algorytm nwd?

Przemysław: No to bycie tych reszt postaci: x*13+y*5 wydaje się jasne z tego algorytmu (jeżeli mogą być x,y ujemne). Dzięki!

Przemysław: Gdyby moje następne pytanie było zbytnim wystawianiem Waszej dobrej woli i cierpliwości na próbę, to nie odpowiadajcie Jak wygląda ogólna metoda postępowania, gdy w układzie kongruencji przy x stoją stałe dowolne, całkowite? coś typu:

⎧	a1*x≡b1 (mod m1)
⎜
⎨	...
⎜
⎩	an*x≡bn (mod mn)

jc: Dzielisz przez a_i (jeśli się da) i powtarzasz dowód Chińskiego twierdzenia o resztach (jeśli się da). Założenia: a_i są względnie pierwsze z m_i, dla dowolnych i≠j, m_i, m_j są względnie pierwsze. Inaczej mogą być kłopoty, np. 2x ≡ 1 (mod 2).

Przemysław: Czyli jeżeli a_i nie jest względnie pierwsze z m_i to będzie sprzeczne? W podanym przez Ciebie przykładzie to to jest sprzeczne, bo nie ma takiej liczby całkowitej, żeby pomnożona przez 2 była nieparzysta.

Przemysław: "to będzie sprzeczne" miało znaczyć, że układ kongruencji będzie sprzeczny

Przemysław: W każdym razie dziękuję