Znaleźć najmniejsze nieujemne rozwiązanie układu kongruencji:
\(\displaystyle{ x\equiv-7\pmod{13}\\
x\equiv39\pmod{15}}\)
Zanleźć rozwiązanie układu kongruencji
-
- Użytkownik
- Posty: 218
- Rejestracja: 12 sty 2011, o 17:05
- Płeć: Kobieta
- Lokalizacja: Polska
Zanleźć rozwiązanie układu kongruencji
Ostatnio zmieniony 15 cze 2011, o 13:46 przez scyth, łącznie zmieniany 2 razy.
Powód: Poprawa wiadomości.
Powód: Poprawa wiadomości.
-
- 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
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}\)
\(\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.
Powód: Poprawa wiadomości.
-
- 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
\(\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}\)
\(\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.- Vax
- 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
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.
\(\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.
-
- Użytkownik
- Posty: 44
- Rejestracja: 9 cze 2015, o 22:41
- Płeć: Mężczyzna
Zanleźć rozwiązanie układu kongruencji
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?
- Premislav
- 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
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??