Rozwiąż układ kongruencji

[anders90]

Witam, mam taki układ do rozwiązania i za bardzo nie wiem jak się za to wziąć. Prosiłbym o wszelką pomoc.

Rozwiąż układ kongruencji:

\(\displaystyle{ \begin{cases} x \equiv 2^{2011} \pmod{21} \\ x \equiv 5 \pmod{11} \\ x \equiv 3 \pmod{5}\end{cases}}\)

Z góry dziękuje za wszelką pomoc!

Pozdrawiam.

[michal17]

wskazówka
\(\displaystyle{ 2 ^{6} \equiv1 \equiv2 ^{2010} (mod 21)}\)
zatem
\(\displaystyle{ x \equiv2 ^{2011} \equiv2 (mod 21)}\)

-- 10 wrz 2011, o 21:56 --

wskazówka 2
Skorzystaj z chińskiego twierdzenia o resztach.

-- 10 wrz 2011, o 22:26 --

Rozwiązanie
Z drugiej kongruencji wynika, że \(\displaystyle{ x=11i+5; i \in N}\)
Zauważmy że dla \(\displaystyle{ i=3}\) spełniona zostaje również trzecia kongruencja.
Zostaje nam do rozważenia układ:

\(\displaystyle{ \begin{cases} x \equiv 2 (mod 21) \\ x \equiv 38 (mod 55) \end{cases}}\)

Z drugiej kongruencji wynika że \(\displaystyle{ x=55l + 38; l \in N}\)
Szukamy takiego l aby zachodziłą również pierwsza kongruencja.

\(\displaystyle{ 55l+38 \equiv13l-4 \equiv2 (mod 21)}\)
Zauważmy że dla \(\displaystyle{ l=15}\) kongruencja jest spełniona

Zatem dla \(\displaystyle{ l=15}\) spełniona jest również 1 kongruencja
Czyli szukaną liczbą jest \(\displaystyle{ x=55 \cdot15 +38=863}\)

[yorgin]

Rozwiązaniem nie jest jedna liczba, a cały zbiór. Zadanie nie podaje, by podać najmniejszą liczbę całkowitą dodatnią.

Dokładniej, każda liczba postaci

\(\displaystyle{ 1155k+863, k\in\mathbb{Z}}\)

jest rozwiązaniem układu.


Samo rozwiązanie przedstawione wyżej jest ok, ale zmierza w kierunku znalezienia jednej konkretnej wartości. Jeśli jednak autorowi tematu to wystarcza, to i ja nie będę się rozpisywać.

[anders90]

hej, dzięki panowie za zainteresowanie:)

jestem w trakcie przypominania sobie materiału po wakacjach do poprawki, więc będę wdzięczny yorgin, jakbyś to rozpisał jakoś tak, żebym odświeżył sobie pamięć i zrozumiał.

[yorgin]

Moja metoda wygląda podobnie, jak poprzednika, pozwolę sobie również wykorzystać jego fragment rachunków, by przejść do uproszczonego układu:

\(\displaystyle{ \begin{cases} x \equiv 2(mod 21) \\ x \equiv 5 (mod 11) \\ x \equiv 3 (mod 5)\end{cases}}\)

Z ostatniego wynika, że

\(\displaystyle{ x=5k+3, k\in\mathbb{Z}}\)

Podstawiasz taką postać do drugiego równania:

\(\displaystyle{ 5k+3\equiv 5\mod 11}\)

skąd kolejno:

\(\displaystyle{ 10l\equiv 4\mod 11\\
k\equiv 7\mod 11}\)

czyli

\(\displaystyle{ k=11l+7, l\in\mathbb{Z}}\)

a stąd wracając z podstawieniami do \(\displaystyle{ x}\):

\(\displaystyle{ x=5(11l+7)+3=55l+38, l\in\mathbb{Z}}\)

Wykorzystamy tą postać do pierwszego równania:

\(\displaystyle{ 55l+38\equiv 2\mod 21}\)

i kolejno:

\(\displaystyle{ 13l\equiv 6 \mod 21 | \cdot 2\\
5l\equiv 12\mod 21 |\cdot 4\\
20l\equiv 48\mod 21\\
-l\equiv 6\mod 21\\
l\equiv 15\mod 21}\)

Zatem

\(\displaystyle{ l=21m+15, m\in\mathbb{Z}}\)

więc ostatecznie

\(\displaystyle{ x=55(21m+15)+38=1155+863m, m\in\mathbb{Z}}\)

[Qń]

Najbardziej elegancka metoda rozwiązywania takich układów kongruencji to metoda niezależnych reszt. Jej omówienie można znaleźć w Matematyce konkretnej (Graham, Knuth, Patashnik) - jest to nieco zgrabniejsze ujęcie tego samego co można znaleźć na Wikipedii.

Q.

[michal17]

Rozwiązaniem nie jest jedna liczba, a cały zbiór. Zadanie nie podaje, by podać najmniejszą liczbę całkowitą dodatnią.

Racja, moje niedopatrzenie.

[anders90]

Najbardziej elegancka metoda rozwiązywania takich układów kongruencji to metoda niezależnych reszt. Jej omówienie można znaleźć w Matematyce konkretnej (Graham, Knuth, Patashnik) - jest to nieco zgrabniejsze ujęcie tego samego co można znaleźć na Wikipedii.

Q.

Qń, mam tą książkę. przeczytałem ten rozdział, ale za bardzo nie wiem jak to zastosować tutaj. czy mógłbyś to jakoś rozpisać? chociaż sam początek?

z góry dzięki!

[Qń]

Mamy do rozwiązania:
\(\displaystyle{ \begin{cases} x \equiv 2 \pmod{21} \\ x \equiv 5 \pmod{11} \\ x \equiv 3 \pmod{5}\end{cases}}\)

Szukamy teraz takich \(\displaystyle{ x_1,x_2,x_3}\), że:
\(\displaystyle{ \begin{cases} x_1 \equiv 1 \pmod{21} \\ x_1 \equiv 0 \pmod{11} \\ x_1 \equiv 0 \pmod{5}\end{cases}}\) \(\displaystyle{ \begin{cases} x_2 \equiv 0 \pmod{21} \\ x_2 \equiv 1 \pmod{11} \\ x_2 \equiv 0 \pmod{5}\end{cases}}\) \(\displaystyle{ \begin{cases} x_3 \equiv 0 \pmod{21} \\ x_3 \equiv 0 \pmod{11} \\ x_3 \equiv 1 \pmod{5}\end{cases}}\)

Rozwiązaniem wyjściowego układu będzie \(\displaystyle{ 2x_1+5x_2+3x_3 \mod 21\cdot 11\cdot 5}\).

Znajdźmy dla przykładu \(\displaystyle{ x_1}\). Skoro jest ono podzielne przez \(\displaystyle{ 11}\) i przez \(\displaystyle{ 5}\), to znaczy, że \(\displaystyle{ x_1=55k}\). Wstawiając to do pierwszej kongruencji dostaniemy:
\(\displaystyle{ 55k \equiv 1 \pmod{21}}\)
czyli
\(\displaystyle{ 13k \equiv 1 \pmod{21}}\)
Łatwo teraz znaleźć \(\displaystyle{ k}\) przy pomocy rozszerzonego algorytmu Euklidesa, a jak znamy \(\displaystyle{ k}\), to znamy też \(\displaystyle{ x_1}\).

Q.

[anders90]

no ok, wyznaczam sobie po kolei \(\displaystyle{ x_{1}, x_{2}, x_{3}}\)
i jeśli się nie pomyliłem nigdzie to będzie to:

\(\displaystyle{ x_{1} = -8 + 21k}\)
\(\displaystyle{ x_{2} = 2 + 11k}\)
\(\displaystyle{ x_{3} = 1 + 5k}\)

podstawiam to sobie pod równanie
\(\displaystyle{ 2x_1+5x_2+3x_3 \mod 21\cdot 11\cdot 5}\).

i wychodzi mi:
\(\displaystyle{ 112k-3 (mod 1155)}\)

dobrze?

przy wszystkich układach kongruencji można śmiało stosować metodę niezależnych reszt?

jeszcze raz dzięki za zainteresowanie i pomoc!

[Qń]

Nie.

Wszystkie \(\displaystyle{ k}\) w sensie w jakim zapisałeś są błędne/niepotrzebne. Przedstawionym wyżej sposobem znajdujemy rozwiązanie \(\displaystyle{ x_0}\) z przedziału \(\displaystyle{ [0, 21 cdot 11 cdot 5)}\), a dopiero jak już to zrobimy, to na samym końcu piszemy, że ogólnym rozwiązaniem jest:
\(\displaystyle{ x=x_0+21 \cdot 11 \cdot 5\cdot k}\)

Ponadto, nawet po pominięciu \(\displaystyle{ k}\), same \(\displaystyle{ x_1,x_2,x_3}\) są wyliczone nieprawidłowo. W którym miejscu podany wyżej sposób wyznaczenia \(\displaystyle{ x_1}\) nie jest jasny?

Q.

[anders90]

\(\displaystyle{ 13k \equiv 1 \pmod{21}}\)

ehh ok już wiem nieco więcej. mówisz że liczymy z rozszerzonego algorytmu ok.
ja licze tak:

\(\displaystyle{ 13k \equiv 1 \pmod{21}}\)

\(\displaystyle{ 13k+21w = 1}\)
\(\displaystyle{ 1 = -8 \cdot 13+5 \cdot 21}\)
\(\displaystyle{ x_{0} = -8}\)
\(\displaystyle{ x = -8 + 21w}\)

co robię źle?

[Qń]

Wyznaczyłeś \(\displaystyle{ k=-8}\), ale pamiętaj, że \(\displaystyle{ x_1=55k}\).

Q.

[95Villain95]

Moja metoda wygląda podobnie, jak poprzednika, pozwolę sobie również wykorzystać jego fragment rachunków, by przejść do uproszczonego układu:

\(\displaystyle{ \begin{cases} x \equiv 2(mod 21) \\ x \equiv 5 (mod 11) \\ x \equiv 3 (mod 5)\end{cases}}\)

Z ostatniego wynika, że

\(\displaystyle{ x=5k+3, k\in\mathbb{Z}}\)

Podstawiasz taką postać do drugiego równania:

\(\displaystyle{ 5k+3\equiv 5\mod 11}\)

skąd kolejno:

\(\displaystyle{ 10l\equiv 4\mod 11\\
k\equiv 7\mod 11}\)

czyli

\(\displaystyle{ k=11l+7, l\in\mathbb{Z}}\)

a stąd wracając z podstawieniami do \(\displaystyle{ x}\):

\(\displaystyle{ x=5(11l+7)+3=55l+38, l\in\mathbb{Z}}\)

Wykorzystamy tą postać do pierwszego równania:

\(\displaystyle{ 55l+38\equiv 2\mod 21}\)

i kolejno:

\(\displaystyle{ 13l\equiv 6 \mod 21 | \cdot 2\\
5l\equiv 12\mod 21 |\cdot 4\\
20l\equiv 48\mod 21\\
-l\equiv 6\mod 21\\
l\equiv 15\mod 21}\)

Zatem

\(\displaystyle{ l=21m+15, m\in\mathbb{Z}}\)

więc ostatecznie

\(\displaystyle{ x=55(21m+15)+38=1155+863m, m\in\mathbb{Z}}\)

Przepraszam za odkopanie, ale czy tutaj wynik nie powinien wynosić
\(\displaystyle{ x=1155m+863, m\in\mathbb{Z}}\)?

[Premislav]

Istotnie.