ukłąd kongurencji

robertos18 · Post autor: **robertos18** » 2 cze 2015, o 19:50

\(\displaystyle{ \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?

Premislav · Post autor: **Premislav** » 2 cze 2015, o 20:02

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

robertos18 · Post autor: **robertos18** » 2 cze 2015, o 20:16

Mam takie cos:
\(\displaystyle{ \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: \(\displaystyle{ 2+3i}\)
najmniejsze takie i, że \(\displaystyle{ x = 2 + 3i}\) dla drugiego równania: Tutaj jestesmy w \(\displaystyle{ Z _{15}}\)

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

Premislav · Post autor: **Premislav** » 2 cze 2015, o 20:43

Tutaj masz to twierdzenie, o którym wspomniałem:
... _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 \(\displaystyle{ x=3l+2}\) dla pewnego \(\displaystyle{ l}\)całkowitego, z drugiego - iż \(\displaystyle{ x=5k+3}\) dla pewnego \(\displaystyle{ k}\) całkowitego, zaś z trzeciego \(\displaystyle{ x=8p+5}\) dla pewnego \(\displaystyle{ p}\) całkowitego. Wtedy otrzymujesz (z przyrównania "iksów"), że \(\displaystyle{ p= \frac{3}{8}(l-1)}\) oraz \(\displaystyle{ k= \frac{1}{5}(3l-1)}\), czyli wystarczy znaleźć takie \(\displaystyle{ l}\) całkowite, iż \(\displaystyle{ 8|(l-1)}\) i \(\displaystyle{ 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 \(\displaystyle{ 3\cdot 5\cdot 8}\).

robertos18 · Post autor: **robertos18** » 2 cze 2015, o 20:59

Czy to jest dobry wynik: \(\displaystyle{ 116 + (3 \cdot 5 \cdot 8)k}\)?

Premislav · Post autor: **Premislav** » 2 cze 2015, o 21:06

Niestety nie, wystarczy podstawić do początkowego układu i widzimy, że to nie jest rozwiązanie. Może błąd w obliczeniach?

robertos18 · Post autor: **robertos18** » 2 cze 2015, o 21:29

Mogłbys zobaczyc w tych moich obliczeniach co zrobiłem zle?

Premislav · Post autor: **Premislav** » 2 cze 2015, o 21:45

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

Nieprawdą jest, że dwa pierwsze równania są równoważne równaniu \(\displaystyle{ x\equiv 11\pmod{15}}\). Trochę nie rozumiem, jak to otrzymałeś.

robertos18 · Post autor: **robertos18** » 2 cze 2015, o 21:56

powinno byc \(\displaystyle{ x\equiv 14\pmod{15}}\)??
Z dwóch pierwszych równań otrzymujemy zatem kongruencję: \(\displaystyle{ x\equiv 14(mod \ 15)}\)
Ogólne rozwiązanie dwóch pierwszych równań to \(\displaystyle{ 14+(3 \cdot 5)j}\)
najmniejsze takie j, że \(\displaystyle{ x = 14 + 15j}\) dla trzeciego równania: Tutaj jestesmy w \(\displaystyle{ Z _{120}}\)
\(\displaystyle{ 14(0),29(1),44(2),60(3),74(4),90(5),104(6),119(7)}\)
Czyli najmniejsze rozwiązanie to \(\displaystyle{ 119}\), a ogólne \(\displaystyle{ 119 + (3 \cdot 5 \cdot 8)k.}\)

Premislav · Post autor: **Premislav** » 2 cze 2015, o 22:49

Dalej jest źle. Układ dwóch pierwszych równań jest równoważny równaniu \(\displaystyle{ x\equiv 8\pmod{15}}\)

robertos18 · Post autor: **robertos18** » 2 cze 2015, o 23:18

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: \(\displaystyle{ 53+120s}\)?

Premislav · Post autor: **Premislav** » 2 cze 2015, o 23:43

OK. Rozważamy taki "podukład":
\(\displaystyle{ \left\{\begin{array}{l} x\equiv 2(mod \ 3) \\x\equiv 3(mod \ 5) \end{array}}\)
z pierwszego równania mamy, że \(\displaystyle{ x=3k+2}\) dla pewnej liczby całkowitej \(\displaystyle{ k}\), zaś z drugiego równania wnioskujemy, że \(\displaystyle{ 5m+3}\) dla pewnego całkowitego \(\displaystyle{ m}\).
Czyli każde liczby \(\displaystyle{ k,l \in \ZZ}\) takie że \(\displaystyle{ 3k+2=5m+3}\) spełniają warunki. Czyli ma być \(\displaystyle{ k= \frac{5}{3}m+ \frac{1}{3}= \frac{1}{3}(5m+1)}\), a zatem potrzeba i wystarcza, by \(\displaystyle{ 3|(5m+1)}\) -bo \(\displaystyle{ k}\) ma być całkowite. Dla \(\displaystyle{ m=1}\) jest to prawda, a dalej wystarczy zauważyć, że jeśli \(\displaystyle{ 5m+1-(5\cdot 1+1)}\) jest podzielne przez trzy, to takie \(\displaystyle{ m}\) spełnia warunki (i na odwrót - gdy różnica ta nie jest podzielna przez \(\displaystyle{ 3}\), to nie może być \(\displaystyle{ 3|(5m'+1)}\)). Czyli \(\displaystyle{ 3t=5m-5}\) dla pewnego \(\displaystyle{ t}\) całkowitego. A zatem \(\displaystyle{ m-1}\) dzieli się przez \(\displaystyle{ 3}\). Czyli \(\displaystyle{ m=3s+1}\), \(\displaystyle{ s}\) dowolne całkowite. Czyli, wracając do układu, \(\displaystyle{ x=5m+3=15s+8}\) dla dowolnego \(\displaystyle{ 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.

robertos18 · Post autor: **robertos18** » 2 cze 2015, o 23:45

Ostateczny wynik to: \(\displaystyle{ 53+120s}\)?

Premislav · Post autor: **Premislav** » 2 cze 2015, o 23:47

Zgadza się.

robertos18 · Post autor: **robertos18** » 2 cze 2015, o 23:48

Dziekuje za pomoc, ale zrobiłem to zupelnie innym sposobem