szukanie zaawansowane
 [ Posty: 15 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 2 cze 2015, o 19:50 
Użytkownik

Posty: 413
Lokalizacja: Torun
\left\{\begin{array}{l} x\equiv 2(mod \ 3) \\2x\equiv 1(mod \ 5)\\x\equiv 5(mod \ 8) \end{array}

W jakis sposób taki układ się rozwiązuje? Czy można zrobic z tego jedno rownanie?
Góra
Mężczyzna Offline
PostNapisane: 2 cze 2015, o 20:02 
Użytkownik

Posty: 12615
3,5 i 8 są parami względnie pierwsze, więc można pomnożyć drugie równanie stronami przez element odwrotny do dwójki w Z_{5}, czyli przez 3 (bo 2\cdot 3\equiv 1\pmod{5}), zredukować współczynnik przy iksie modulo 5 w tym drugim równaniu, a potem do tak przekształconego układu zastosować chińskie twierdzenie o resztach.
Góra
Mężczyzna Offline
PostNapisane: 2 cze 2015, o 20:16 
Użytkownik

Posty: 413
Lokalizacja: Torun
Mam takie cos:
\left\{\begin{array}{l} x\equiv 2(mod \ 3) \\x\equiv 3(mod \ 5)\\x\equiv 5(mod \ 8) \end{array}

Ogólne rozwiązanie pierwszego równania to: 2+3i
najmniejsze takie i, że x = 2 + 3i dla drugiego równania: Tutaj jestesmy w Z _{15}

2(0),5(1),11(3)
Najmniejsze takie i to 3.
Z dwóch pierwszych równań otrzymujemy zatem kongruencję: x\equiv 11(mod \ 15)
Ogólne rozwiązanie dwóch pierwszych równań to 11+(3 \cdot 5)j
najmniejsze takie j, że x = 11 + 15j dla trzeciego równania: Tutaj jestesmy w Z _{120}
11(0),26(1),41(2),56(3),71(4),86(5),101(6),116(7)
Prosze o sprawdzenie
Czyli najmniejsze rozwiązanie to 116, a ogólne 116 + (3  \cdot  5  \cdot  8)k.
Góra
Mężczyzna Offline
PostNapisane: 2 cze 2015, o 20:43 
Użytkownik

Posty: 12615
Tutaj masz to twierdzenie, o którym wspomniałem:
http://en.wikipedia.org/wiki/Chinese_re ... _statement
(nie podlinkowałem polskiej wersji, bo zdaje się, że było tam jakieś oskarżenie o plagiat, czy coś, albo to ja nie umiem czytać).

Ale nie jest konieczne użycie go, gdy już masz taką postać układu (choc jest wygodne).
Z pierwszego równania masz, że x=3l+2 dla pewnego lcałkowitego, z drugiego - iż x=5k+3 dla pewnego k całkowitego, zaś z trzeciego x=8p+5 dla pewnego p całkowitego. Wtedy otrzymujesz (z przyrównania "iksów"), że p= \frac{3}{8}(l-1) oraz k= \frac{1}{5}(3l-1), czyli wystarczy znaleźć takie l całkowite, iż 8|(l-1) i 5|(3l-1), co można zrobić w pamięci. No a to całe twierdzenie gwarantuje, że jest to jedyne rozwiązanie układu modulo 3\cdot 5\cdot 8.
Góra
Mężczyzna Offline
PostNapisane: 2 cze 2015, o 20:59 
Użytkownik

Posty: 413
Lokalizacja: Torun
Czy to jest dobry wynik: 116 + (3 \cdot 5 \cdot 8)k?
Góra
Mężczyzna Offline
PostNapisane: 2 cze 2015, o 21:06 
Użytkownik

Posty: 12615
Niestety nie, wystarczy podstawić do początkowego układu i widzimy, że to nie jest rozwiązanie. Może błąd w obliczeniach?
Góra
Mężczyzna Offline
PostNapisane: 2 cze 2015, o 21:29 
Użytkownik

Posty: 413
Lokalizacja: Torun
Mogłbys zobaczyc w tych moich obliczeniach co zrobiłem zle?
Góra
Mężczyzna Offline
PostNapisane: 2 cze 2015, o 21:45 
Użytkownik

Posty: 12615
A, nie zauważyłem, że edytowałeś posta. Łokiej.

Nieprawdą jest, że dwa pierwsze równania są równoważne równaniu x\equiv 11\pmod{15}. Trochę nie rozumiem, jak to otrzymałeś.
Góra
Mężczyzna Offline
PostNapisane: 2 cze 2015, o 21:56 
Użytkownik

Posty: 413
Lokalizacja: Torun
powinno byc x\equiv 14\pmod{15}??
Z dwóch pierwszych równań otrzymujemy zatem kongruencję: x\equiv 14(mod \ 15)
Ogólne rozwiązanie dwóch pierwszych równań to 14+(3 \cdot 5)j
najmniejsze takie j, że x = 14 + 15j dla trzeciego równania: Tutaj jestesmy w Z _{120}
14(0),29(1),44(2),60(3),74(4),90(5),104(6),119(7)
Czyli najmniejsze rozwiązanie to 119, a ogólne 119 + (3  \cdot  5  \cdot  8)k.
Góra
Mężczyzna Offline
PostNapisane: 2 cze 2015, o 22:49 
Użytkownik

Posty: 12615
Dalej jest źle. Układ dwóch pierwszych równań jest równoważny równaniu x\equiv 8\pmod{15}
Góra
Mężczyzna Offline
PostNapisane: 2 cze 2015, o 23:18 
Użytkownik

Posty: 413
Lokalizacja: Torun
Nie rozumiem jak do tego doszedłes, mogłbys mi przyblizyc Twoj algorytm rozwiazywania tego?

-- 2 cze 2015, o 23:42 --

Dobra juz zrozumialem wynik to: 53+120s?
Góra
Mężczyzna Offline
PostNapisane: 2 cze 2015, o 23:43 
Użytkownik

Posty: 12615
OK. Rozważamy taki "podukład":
\left\{\begin{array}{l} x\equiv 2(mod \ 3) \\x\equiv 3(mod \ 5) \end{array}
z pierwszego równania mamy, że x=3k+2 dla pewnej liczby całkowitej k, zaś z drugiego równania wnioskujemy, że 5m+3 dla pewnego całkowitego m.
Czyli każde liczby k,l \in \ZZ takie że 3k+2=5m+3 spełniają warunki. Czyli ma być k= \frac{5}{3}m+ \frac{1}{3}= \frac{1}{3}(5m+1), a zatem potrzeba i wystarcza, by 3|(5m+1) -bo k ma być całkowite. Dla m=1 jest to prawda, a dalej wystarczy zauważyć, że jeśli 5m+1-(5\cdot 1+1) jest podzielne przez trzy, to takie m spełnia warunki (i na odwrót - gdy różnica ta nie jest podzielna przez 3, to nie może być 3|(5m'+1)). Czyli 3t=5m-5 dla pewnego t całkowitego. A zatem m-1 dzieli się przez 3. Czyli m=3s+1, s dowolne całkowite. Czyli, wracając do układu, x=5m+3=15s+8 dla dowolnego s całkowitego.
Trochę (a nawet bardzo) to pałkarskie, ale już trudno.
Chociaż mój prawdziwy algorytm to było zgadnięcie rozwiązania. :twisted:
Góra
Mężczyzna Offline
PostNapisane: 2 cze 2015, o 23:45 
Użytkownik

Posty: 413
Lokalizacja: Torun
Ostateczny wynik to: 53+120s?
Góra
Mężczyzna Offline
PostNapisane: 2 cze 2015, o 23:47 
Użytkownik

Posty: 12615
Zgadza się.
Góra
Mężczyzna Offline
PostNapisane: 2 cze 2015, o 23:48 
Użytkownik

Posty: 413
Lokalizacja: Torun
Dziekuje za pomoc, ale zrobiłem to zupelnie innym sposobem :D
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 15 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 układ kongurencji - zadanie 4  kasia00  13
 Układ kongurencji  Kanodelo  1
 Układ kongurencji - zadanie 2  Kanodelo  8
 układ modularny  matematyka464  1
 Kongruencja - rozwiązać układ  blazejp  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl