Układ kongruencji - w jaki sposób został uzyskany ten wynik?

[Scrub]

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?

[Takahashi]

Chińskie twierdzenie o resztach.

[Scrub]

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]

\(\displaystyle{ 158 = 15 \cdot 10 + 8}\), więc Twoje rozwiązanie nie spełnia pierwszego równania.

[Scrub]

No wiem że jest źle. Chciałbym się dowiedzieć jak to prawidłowo obliczyć.

[Takahashi]

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}\).

[Scrub]

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) \\}\)
?

[Takahashi]

No tak, ale \(\displaystyle{ 22 \equiv_3 1}\) oraz \(\displaystyle{ 22 \equiv_4 2}\), więc to co dalej napisałem ma sens.

[Scrub]

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ć.

[Takahashi]

Mylisz gdzieś znak, bo \(\displaystyle{ 34}\) spełnia układ, w którym prawe strony to: \(\displaystyle{ 1, -1, 2}\).

[Scrub]

Nie ogarniam, mógłbyś zrobić ten przykład?

[Takahashi]

Pokaż obliczenia, wskażę Ci miejsce, gdzie robisz błąd.

[Scrub]

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}\)

[Takahashi]

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}\).

[Scrub]

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?