Rozwiązanie układu kongurencji

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
bart1141
Użytkownik
Użytkownik
Posty: 3
Rejestracja: 31 sty 2010, o 19:19
Płeć: Mężczyzna
Lokalizacja: polska
Podziękował: 1 raz

Rozwiązanie układu kongurencji

Post autor: bart1141 »

mam prośbę o pomoc w rozwiązaniu kongurencji krok po kroku gdyż przygotowuje się do egzaminu a nie mam pojęcia jak do tego się zabrać z góry dzięki a tu przykład:
\(\displaystyle{ \begin{cases}
x\equiv 9\; \text{(mod 11)}\\
x\equiv 6\; \text{(mod 13)}\\
x\equiv 6\; \text{(mod 12)}\\
x\equiv 9\; \text{(mod 15)}\\
\end{cases}}\)
Ostatnio zmieniony 22 sie 2010, o 19:02 przez Althorion, łącznie zmieniany 2 razy.
Powód: Niepoprawnie napisany kod LaTeX-a. Proszę zapoznaj się z http://matematyka.pl/178502.htm .
justynian
Użytkownik
Użytkownik
Posty: 705
Rejestracja: 10 lip 2009, o 16:32
Płeć: Mężczyzna
Podziękował: 21 razy
Pomógł: 58 razy

Rozwiązanie układu kongurencji

Post autor: justynian »

nawet gdybyś wygooglal chińskie twierdzenie o resztach to już by było po problemie
Awatar użytkownika
SaxoN
Użytkownik
Użytkownik
Posty: 154
Rejestracja: 20 cze 2008, o 14:33
Płeć: Mężczyzna
Lokalizacja: Katowice/ Warszawa
Podziękował: 3 razy
Pomógł: 9 razy

Rozwiązanie układu kongurencji

Post autor: SaxoN »

Ja bym dla pierwszych trzech kongruencji zastosował ... o_resztach , dalej powinno pójść z górki A może opisany tam algorytm da się rozszerzyć na liczby, które nie są względnie pierwsze? Tego nie wiem, na razie nie chce mi się tego czytać xD

Edit: Troszkę za późno
Awatar użytkownika
Mariusz M
Użytkownik
Użytkownik
Posty: 6903
Rejestracja: 25 wrz 2007, o 01:03
Płeć: Mężczyzna
Lokalizacja: 53°02'N 18°35'E
Podziękował: 2 razy
Pomógł: 1246 razy

Rozwiązanie układu kongurencji

Post autor: Mariusz M »

No od razu nie da się zastosować chińskiego twierdzenia o resztach trzeba ten układ trochę poprzekształcać
(moduły nie są parami względnie pierwsze)

\(\displaystyle{ \begin{cases}
x\equiv 9(mod11)\\
x\equiv 6(mod13)\\
x\equiv 0(mod 3)\\
x\equiv 2(mod 4)\\
x\equiv 4(mod 5)\\
\end{cases}}\)


i teraz chińskie twierdzenie o resztach
(Algorytm Euklidesa kombinacja liniowa modułów itd)

\(\displaystyle{ x=2814+8580 \cdot k}\)
Ostatnio zmieniony 23 sie 2010, o 07:04 przez Mariusz M, łącznie zmieniany 1 raz.
Awatar użytkownika
SaxoN
Użytkownik
Użytkownik
Posty: 154
Rejestracja: 20 cze 2008, o 14:33
Płeć: Mężczyzna
Lokalizacja: Katowice/ Warszawa
Podziękował: 3 razy
Pomógł: 9 razy

Rozwiązanie układu kongurencji

Post autor: SaxoN »

No i działa ^^ Tzn. to chyba jest oczywiste, ale od razu napiszę, że mariuszm wykorzystał po prostu \(\displaystyle{ x\equiv a\pmod{mn}\Rightarrow x\equiv a\pmod{n}}\).
xyz90
Użytkownik
Użytkownik
Posty: 43
Rejestracja: 25 paź 2009, o 10:06
Płeć: Kobieta
Lokalizacja: kraina marzeń

Rozwiązanie układu kongurencji

Post autor: xyz90 »

Mamy układ:

x equiv 3 (mod 4)
x equiv 4 (mod 5)
x equiv 1 (mod 7)

Używając metody generowania kolejnych wielokrotności (która jest mało wydajnym algorytmem, aczkolwiek prawdopodobnie najlepszym do liczenia na kartce):

Ogólne rozwiązanie pierwszego równania to 3 + 4i
Znajdujemy najmniejsze i, takie że x = 3 + 4i spełnia drugie równanie:

3 (0), 7 (1), 11 (2), 15 (3), 19 (4)
Najmniejsze takie i to 4

Z dwóch pierwszych równań otrzymujemy zatem x equiv 19 (mod 20)
Ogólne rozwiązanie dwóch pierwszych równań to 19 + (4 imes 5)j
Znajdujemy najmniejsze j, takie że x = 19 + 20j spełnia trzecie równanie:

19 (0), 39 (1), 59 (2), 79 (3), 99 (4)

Czyli najmniejsze rozwiązanie to 99, a ogólne 99 + (4 imes 5 imes 7)k
czy mozecie mi powiedziec jak powstala ta pogrubiona linijka?
justynian
Użytkownik
Użytkownik
Posty: 705
Rejestracja: 10 lip 2009, o 16:32
Płeć: Mężczyzna
Podziękował: 21 razy
Pomógł: 58 razy

Rozwiązanie układu kongurencji

Post autor: justynian »

w nawiasach jest co podstawiono za i a przed nawiasami wynik dla takiego i.
ODPOWIEDZ