Zanleźć rozwiązanie układu kongruencji

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
madziula1784
Użytkownik
Użytkownik
Posty: 218
Rejestracja: 12 sty 2011, o 17:05
Płeć: Kobieta
Lokalizacja: Polska

Zanleźć rozwiązanie układu kongruencji

Post autor: madziula1784 »

Znaleźć najmniejsze nieujemne rozwiązanie układu kongruencji:
\(\displaystyle{ x\equiv-7\pmod{13}\\
x\equiv39\pmod{15}}\)
Ostatnio zmieniony 15 cze 2011, o 13:46 przez scyth, łącznie zmieniany 2 razy.
Powód: Poprawa wiadomości.
Kartezjusz
Użytkownik
Użytkownik
Posty: 7330
Rejestracja: 14 lut 2008, o 08:31
Płeć: Mężczyzna
Lokalizacja: Z Bielskia-Białej
Podziękował: 6 razy
Pomógł: 961 razy

Zanleźć rozwiązanie układu kongruencji

Post autor: Kartezjusz »

Nasz \(\displaystyle{ x}\) jest postaci:
\(\displaystyle{ x=13t-7}\) i \(\displaystyle{ x=15u+9}\). pomnóżmy I równanie przez \(\displaystyle{ 15}\), a drugie przez \(\displaystyle{ 13}\) i mamy
\(\displaystyle{ 15x=105\pmod {13 \cdot 15} \\
13x=117\pmod {13 \cdot 15}}\)

Odejmijmy stronami:
\(\displaystyle{ 2x=-12 \pmod{13 \cdot 15}\\
x=-6\pmod{13 \cdot 15}}\)

\(\displaystyle{ x=195-6}\), bo rozwiązanie ma być nieujemne
\(\displaystyle{ x=189}\)
Ostatnio zmieniony 13 wrz 2018, o 00:23 przez Jan Kraszewski, łącznie zmieniany 2 razy.
Powód: Poprawa wiadomości.
kolorowe skarpetki
Użytkownik
Użytkownik
Posty: 400
Rejestracja: 11 cze 2010, o 11:25
Płeć: Kobieta
Lokalizacja: Gdynia
Pomógł: 64 razy

Zanleźć rozwiązanie układu kongruencji

Post autor: kolorowe skarpetki »

\(\displaystyle{ \begin{cases} x \equiv -7 (mod 13) \\ x \equiv 39 (mod 15) \end{cases}}\)
\(\displaystyle{ n_1=13,n_2=15,a_1=-7,a_2=39}\)
Liczby 13,15 są względnie pierwsze a zatem układ ma jedno rozwiązanie modulo \(\displaystyle{ n}\) :
(1) \(\displaystyle{ n=n_1 \cdot n_2 = 13 \cdot 15 = 195}\)
(2) Wyznaczamy \(\displaystyle{ N_1,N_2 : n=n_1 \cdot N_1=n_2 \cdot N_2 , NWD(n_i,N_i)=1 :}\)
\(\displaystyle{ n=13 \cdot 15 = 15 \cdot 13 \Rightarrow N_1=15,N_2=13}\)
(3) Szukamy liczb \(\displaystyle{ N_i'}\) z równań : \(\displaystyle{ N_i \cdot N_i ' \equiv 1 (mod n_i)}\)
\(\displaystyle{ (31) \, 15 \cdot N_1' \equiv 1 (mod 13)}\)
\(\displaystyle{ 15 \cdot N_1' \equiv -12 (mod 13)}\)
\(\displaystyle{ 5 \cdot N_1' \cdot 3 \equiv -4 \cdot 3 (mod 13)}\)
\(\displaystyle{ 5 \cdot N_1' \equiv -4 (mod 13)}\)
\(\displaystyle{ 25 \cdot N_1' \equiv -20 (mod 13)}\)
\(\displaystyle{ N_1' \equiv 20 (mod 13) \equiv 7 (mod 13)}\)
\(\displaystyle{ (32) \, 13 \cdot N_2' \equiv 1 (mod 15) \, \Rightarrow \, N_2' \equiv 7 (mod 15)}\)
\(\displaystyle{ (4) x_0 \equiv ( N_1 \cdot N_1' \cdot a_1 + N_2 \cdot N_2' \cdot a_2)\, (mod n)}\)
\(\displaystyle{ x_0 \equiv 1449 (mod \, 195) \equiv 84 (mod 195)}\)
Odp. \(\displaystyle{ x_0=84}\)
P.S. Liczba 189 nie przystaje do liczby -7 modulo 13.
Awatar użytkownika
Vax
Użytkownik
Użytkownik
Posty: 2913
Rejestracja: 27 kwie 2010, o 22:07
Płeć: Mężczyzna
Lokalizacja: Biała Podlaska / Warszawa
Podziękował: 4 razy
Pomógł: 612 razy

Zanleźć rozwiązanie układu kongruencji

Post autor: Vax »

Po prostu Kartezjusz zapomniał o minusie, rozumowanie jest prawidłowe, a sposób szybszy niż przedstawiony wyżej:

\(\displaystyle{ \begin{cases} x\equiv -7\pmod{13} /\cdot 15\\ x\equiv 39 \equiv 9\pmod{15}/\cdot 13 \end{cases}}\)

\(\displaystyle{ \begin{cases} 15x \equiv 90\pmod{13\cdot 15}\\ 13x \equiv 117\pmod{13\cdot 15} \end{cases}}\)

Odejmujemy stronami:

\(\displaystyle{ 2x \equiv 168 \pmod{13\cdot 15}}\)

\(\displaystyle{ x \equiv 84 \pmod{13\cdot 15}}\)

Ale x ma być najmniejszą liczbą nieujemną, która spełnia daną kongruencje skąd \(\displaystyle{ x = 84}\)

Pozdrawiam.
WhiteRabbit7
Użytkownik
Użytkownik
Posty: 44
Rejestracja: 9 cze 2015, o 22:41
Płeć: Mężczyzna

Zanleźć rozwiązanie układu kongruencji

Post autor: WhiteRabbit7 »

Czy zawsze można używać sposobu przedstawionego przez Vax, nawet przy 3 równaniach w układzie, licząc najpierw dwa pierwsze, a następnie do rozwiązania dodając 3 układ i ponownie otrzymując układ z dwoma równaniami liczyć tym sposobem?
Awatar użytkownika
Premislav
Użytkownik
Użytkownik
Posty: 15685
Rejestracja: 17 sie 2012, o 13:12
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 195 razy
Pomógł: 5219 razy

Zanleźć rozwiązanie układu kongruencji

Post autor: Premislav »

Tak. Jeśli masz układ \(\displaystyle{ k}\) kongruencji, to jego ogólne rozwiązanie musi być w szczególności pewnym rozwiązaniem każdego podukładu. Czyli przykładowo rozwiązanie ogólne układu \(\displaystyle{ 3}\) kongruencji musi być pewnym rozwiązaniem podukładu złożonego z dwóch pierwszych kongruencji itp.-- 14 kwi 2016, o 02:29 --rotfl, teraz patrzę, po co mi było to \(\displaystyle{ k}\). Żeby mądrzej brzmiało??
PanPrezes
Użytkownik
Użytkownik
Posty: 1
Rejestracja: 12 wrz 2018, o 22:29
Płeć: Mężczyzna
Lokalizacja: Rzeszów

Zanleźć rozwiązanie układu kongruencji

Post autor: PanPrezes »

A co jeśli x wychodzi ujemne?
ODPOWIEDZ