Układ kongruencji - w jaki sposób został uzyskany ten wynik?
Układ kongruencji - w jaki sposób został uzyskany ten wynik?
Układ:
\(\displaystyle{ \begin{cases}
x \equiv 1 (mod 15)
\\
x \equiv 22 (mod 36)
\end{cases}}\)
Wynik: \(\displaystyle{ x = 166 + k \cdot 180}\)
Mógłby ktoś wytłumaczyć krok po kroku skąd to się wzięło?
\(\displaystyle{ \begin{cases}
x \equiv 1 (mod 15)
\\
x \equiv 22 (mod 36)
\end{cases}}\)
Wynik: \(\displaystyle{ x = 166 + k \cdot 180}\)
Mógłby ktoś wytłumaczyć krok po kroku skąd to się wzięło?
Re: Układ kongruencji - w jaki sposób został uzyskany ten wy
Tyle wiem, "umiem" to rozłożyć na moduły względnie pierwsze (moduły: 3, 5, 4, 3, 3) i rozwiązać, ale wychodzi mi \(\displaystyle{ x = 158 + k \cdot 180}\)
- Takahashi
- Użytkownik
- Posty: 186
- Rejestracja: 12 maja 2017, o 19:04
- Płeć: Mężczyzna
- Lokalizacja: brak
- Podziękował: 1 raz
- Pomógł: 22 razy
Re: Układ kongruencji - w jaki sposób został uzyskany ten wy
\(\displaystyle{ 158 = 15 \cdot 10 + 8}\), więc Twoje rozwiązanie nie spełnia pierwszego równania.
Re: Układ kongruencji - w jaki sposób został uzyskany ten wy
No wiem że jest źle. Chciałbym się dowiedzieć jak to prawidłowo obliczyć.
- Takahashi
- Użytkownik
- Posty: 186
- Rejestracja: 12 maja 2017, o 19:04
- Płeć: Mężczyzna
- Lokalizacja: brak
- Podziękował: 1 raz
- Pomógł: 22 razy
Re: Układ kongruencji - w jaki sposób został uzyskany ten wy
Szukamy \(\displaystyle{ x}\) takiego, że \(\displaystyle{ x \equiv_3 1}\), \(\displaystyle{ x \equiv_5 1}\) i \(\displaystyle{ x \equiv_4 = 2}\). Zatem \(\displaystyle{ x \equiv_{15} 1}\) i musimy rozwiązać dwie względnie pierwsze kongruencje.
Jeśli nie znasz rozszerzonego algorytmu Euklidesa, po prostu licz reszty z dzielenia przez \(\displaystyle{ 4}\) liczb \(\displaystyle{ 16, 31, 46, 61, \ldots}\). Wyjdzie Ci, że \(\displaystyle{ x \equiv_{60} 46}\), czyli \(\displaystyle{ x = 60k + 46}\).
Jeśli nie znasz rozszerzonego algorytmu Euklidesa, po prostu licz reszty z dzielenia przez \(\displaystyle{ 4}\) liczb \(\displaystyle{ 16, 31, 46, 61, \ldots}\). Wyjdzie Ci, że \(\displaystyle{ x \equiv_{60} 46}\), czyli \(\displaystyle{ x = 60k + 46}\).
Re: Układ kongruencji - w jaki sposób został uzyskany ten wy
Dwie pierwsze kongruencje które napisałeś rozumiem, a dalej nie. Czy nie powinno być
\(\displaystyle{ x \equiv 1 (mod 3) \\
x \equiv 1 (mod 5) \\
x \equiv 22 (mod 4) \\
x \equiv 22 (mod 3) \\}\)
?
\(\displaystyle{ x \equiv 1 (mod 3) \\
x \equiv 1 (mod 5) \\
x \equiv 22 (mod 4) \\
x \equiv 22 (mod 3) \\}\)
?
- Takahashi
- Użytkownik
- Posty: 186
- Rejestracja: 12 maja 2017, o 19:04
- Płeć: Mężczyzna
- Lokalizacja: brak
- Podziękował: 1 raz
- Pomógł: 22 razy
Re: Układ kongruencji - w jaki sposób został uzyskany ten wy
No tak, ale \(\displaystyle{ 22 \equiv_3 1}\) oraz \(\displaystyle{ 22 \equiv_4 2}\), więc to co dalej napisałem ma sens.
Układ kongruencji - w jaki sposób został uzyskany ten wynik?
Rzeczywiście, czyli mamy:
\(\displaystyle{ x \equiv 1 (mod 3) \\ x \equiv 1 (mod 5) \\ x \equiv 2 (mod 4) \\ x \equiv 1 (mod 3) \\}\)
to co się powtarza usuwam:
\(\displaystyle{ x \equiv 1 (mod 3) \\ x \equiv 1 (mod 5) \\ x \equiv 2 (mod 4) \\}\)
Dobrze? Po wyliczeniu tego układu znowu mam inny wynik: \(\displaystyle{ 34 + 60k}\) ;_;
Rozszerzony alg Euklidesa ogarniam, ale nie wiem jak go tu wykorzystać.
\(\displaystyle{ x \equiv 1 (mod 3) \\ x \equiv 1 (mod 5) \\ x \equiv 2 (mod 4) \\ x \equiv 1 (mod 3) \\}\)
to co się powtarza usuwam:
\(\displaystyle{ x \equiv 1 (mod 3) \\ x \equiv 1 (mod 5) \\ x \equiv 2 (mod 4) \\}\)
Dobrze? Po wyliczeniu tego układu znowu mam inny wynik: \(\displaystyle{ 34 + 60k}\) ;_;
Rozszerzony alg Euklidesa ogarniam, ale nie wiem jak go tu wykorzystać.
- Takahashi
- Użytkownik
- Posty: 186
- Rejestracja: 12 maja 2017, o 19:04
- Płeć: Mężczyzna
- Lokalizacja: brak
- Podziękował: 1 raz
- Pomógł: 22 razy
Re: Układ kongruencji - w jaki sposób został uzyskany ten wy
Mylisz gdzieś znak, bo \(\displaystyle{ 34}\) spełnia układ, w którym prawe strony to: \(\displaystyle{ 1, -1, 2}\).
Re: Układ kongruencji - w jaki sposób został uzyskany ten wy
Nie ogarniam, mógłbyś zrobić ten przykład?
Układ kongruencji - w jaki sposób został uzyskany ten wynik?
Zadanie:
\(\displaystyle{ \begin{cases} x \equiv 1 (mod 15) \\ x \equiv 22 (mod 36) \end{cases}}\)
Rozwiązanie:
->
\(\displaystyle{ \begin{cases}
x \equiv 1 (mod 5) \\
x \equiv 1 (mod 3) \\
x \equiv 22 (mod 4) \\
x \equiv 22 (mod 9) \\
\end{cases}}\)
->
\(\displaystyle{ \begin{cases}
x \equiv 1 (mod 5) \\
x \equiv 1 (mod 3) \\
x \equiv 22 (mod 4) \\
x \equiv 22 (mod 3) \\
x \equiv 22 (mod 3) \\
\end{cases}}\)
->
\(\displaystyle{ \begin{cases}
x \equiv 1 (mod 5) \\
x \equiv 1 (mod 3) \\
x \equiv 2 (mod 4) \\
x \equiv 1 (mod 3) \\
x \equiv 1 (mod 3) \\
\end{cases}}\)
->
Usuwam powtarzające się kongruencje
\(\displaystyle{ \begin{cases}
x \equiv 1 (mod 5) \\
x \equiv 1 (mod 3) \\
x \equiv 2 (mod 4) \\
\end{cases}}\)
Obliczam 2 pierwsze:
\(\displaystyle{ 1+3(1+5k)=4+15k}\)
-> mamy
\(\displaystyle{ \begin{cases}
x \equiv 4 (mod 15) \\
x \equiv 2 (mod 4) \\
\end{cases}}\)
ostatecznie: \(\displaystyle{ 4+15(2+4k)=34+60k}\)
\(\displaystyle{ \begin{cases} x \equiv 1 (mod 15) \\ x \equiv 22 (mod 36) \end{cases}}\)
Rozwiązanie:
->
\(\displaystyle{ \begin{cases}
x \equiv 1 (mod 5) \\
x \equiv 1 (mod 3) \\
x \equiv 22 (mod 4) \\
x \equiv 22 (mod 9) \\
\end{cases}}\)
->
\(\displaystyle{ \begin{cases}
x \equiv 1 (mod 5) \\
x \equiv 1 (mod 3) \\
x \equiv 22 (mod 4) \\
x \equiv 22 (mod 3) \\
x \equiv 22 (mod 3) \\
\end{cases}}\)
->
\(\displaystyle{ \begin{cases}
x \equiv 1 (mod 5) \\
x \equiv 1 (mod 3) \\
x \equiv 2 (mod 4) \\
x \equiv 1 (mod 3) \\
x \equiv 1 (mod 3) \\
\end{cases}}\)
->
Usuwam powtarzające się kongruencje
\(\displaystyle{ \begin{cases}
x \equiv 1 (mod 5) \\
x \equiv 1 (mod 3) \\
x \equiv 2 (mod 4) \\
\end{cases}}\)
Obliczam 2 pierwsze:
\(\displaystyle{ 1+3(1+5k)=4+15k}\)
-> mamy
\(\displaystyle{ \begin{cases}
x \equiv 4 (mod 15) \\
x \equiv 2 (mod 4) \\
\end{cases}}\)
ostatecznie: \(\displaystyle{ 4+15(2+4k)=34+60k}\)
- Takahashi
- Użytkownik
- Posty: 186
- Rejestracja: 12 maja 2017, o 19:04
- Płeć: Mężczyzna
- Lokalizacja: brak
- Podziękował: 1 raz
- Pomógł: 22 razy
Re: Układ kongruencji - w jaki sposób został uzyskany ten wy
Nie wiem jakim algorytmem to liczysz, ale jest błąd... By znaleźć rozwiązanie układu \(\displaystyle{ x = a_1 \mod n_1}\), \(\displaystyle{ x = a_2 \mod n_2}\), skorzystamy z tożsamości Bezouta. Mówi o istnieniu liczb \(\displaystyle{ m_1, m_2}\) takich, że \(\displaystyle{ m_1n_1 + m_2n_2 = 1}\). Rozwiązaniem pierwotnego układu jest wtedy \(\displaystyle{ x = a_1m_2n_2 + a_2m_1n_1}\) (możesz się o tym przekonać niemalże na palcach).
U nas \(\displaystyle{ a_1 = 1}\), \(\displaystyle{ n_1 = 5}\), \(\displaystyle{ a_2 = 1}\), \(\displaystyle{ n_2 = 3}\), dlatego musimy najpierw rozwiązać równanie \(\displaystyle{ 5m_1 + 3m_2 = 1}\). Okej, to jest proste, \(\displaystyle{ m_1 = 2}\), \(\displaystyle{ m_2 = -3}\) (na przykład). To daje nam \(\displaystyle{ x = \ldots}\).
U nas \(\displaystyle{ a_1 = 1}\), \(\displaystyle{ n_1 = 5}\), \(\displaystyle{ a_2 = 1}\), \(\displaystyle{ n_2 = 3}\), dlatego musimy najpierw rozwiązać równanie \(\displaystyle{ 5m_1 + 3m_2 = 1}\). Okej, to jest proste, \(\displaystyle{ m_1 = 2}\), \(\displaystyle{ m_2 = -3}\) (na przykład). To daje nam \(\displaystyle{ x = \ldots}\).
Układ kongruencji - w jaki sposób został uzyskany ten wynik?
Niestety nie słyszałem o tym :/ Mam krótki opis rozwiązania tego zadania i tam jest chyba inne podejście, ale nie wiem czy mogę udostępniać te materiały publicznie, jak wyślę na pw rzuciłbyś okiem?