Rozwiązać układ kongruencji

[Eclipt]

Witam. Za zadanie mam wyznaczyć rozwiązania następującego układu:
\(\displaystyle{ \begin{cases}
x\equiv 7 (mod \ 9)\\
x\equiv 2 (mod \ 10)\\
x\equiv 3 (mod \ 12)\\
x\equiv 6 (mod \ 15)
\end{cases}}\)

Najpierw sprowadzam kongruencje do "wspólnego modulo":
\(\displaystyle{ NWW(9, 10, 12, 15)=180}\)
Pierwszą kongruencję mnożę przez 20, drugą przez 18, trzecią przez 15, czwartą przez 12:
\(\displaystyle{ \begin{cases}
20x\equiv 140 (mod \ 180)\\
18x\equiv 36 (mod \ 180)\\
15x\equiv 45 (mod \ 180)\\
12x\equiv 72 (mod \ 180)
\end{cases}}\)

Teraz od drugiej kongruencji odejmuję pierwszą, dodaję trzecią i odejmuję czwartą (2. -1. +3. -4.)
\(\displaystyle{ x\equiv -131 (mod \ 180)}\) czyli \(\displaystyle{ x\equiv 49 (mod \ 180)}\)
Stąd wychodzi, że:
\(\displaystyle{ x=180n+49 \ \ n \in Z}\)

Co, zgodnie z prawami Murphy`ego jest odpowiedzią niepoprawną (z drugiej kongruencji wynika, że ostatnią cyfrą wyniku musi być 2). Gdzie popełniem błąd? Metoda jest niepoprawna czy pomyliłem się w obliczeniach? Jak powinno się rozwiązywać taki układ?

[Sylwek]

Z drugiej kongruencji wnosimy, że x jest parzyste, a z trzeciej, że jest nieparzyste - sprzeczność

[Eclipt]

Jakby się uważniej przypatrzeć to faktycznie:
z drugiej:
\(\displaystyle{ x=10n+2}\)
z trzeciej:
\(\displaystyle{ x=12m+3}\)
Czyli zadanie-podpucha, albo prowadzący ćwiczenia się pomylił przy konstruowaniu zadania (przepisałem na pewno dobrze) .

To może zadanie z innego kolokwium. Polecenie to samo:
\(\displaystyle{ \begin{cases}
x\equiv 2 (mod \ 14)\\
x\equiv 16 (mod \ 21)\\
x\equiv 10 (mod \ 30)\\
\end{cases}}\)

Tym razem takiej podpuchy nie ma, bo z pierwszego i trzeciego x jest parzyste, a z drugiego nie wiadomo. Robiąc je tą samą metodą:
\(\displaystyle{ NWW(14, 21, 30)=210}\)
Pierwszą kongruencję mnożę przez 15, drugą przez 10, trzecią przez 7:
\(\displaystyle{ \begin{cases}
15x\equiv 30 (mod \ 210)\\
10x\equiv 160 (mod \ 210)\\
7x\equiv 70 (mod \ 210)\\
\end{cases}}\)
Teraz niewiadomą i resztę w kongruencji pierwszej mnożę przez 2, a w trzeciej przez 3:
\(\displaystyle{ \begin{cases}
30x\equiv 60 (mod \ 210)\\
10x\equiv 160 (mod \ 210)\\
21x\equiv 210 (mod \ 210) \ -> \ 21x\equiv 0(mod \ 210)\\
\end{cases}}\)
Do kongruencji trzeciej dodaję drugą i odejmuję pierwszą:
\(\displaystyle{ x\equiv 100 (mod \ 210)}\)
Czyli:
\(\displaystyle{ x=210n + 100 \ ;n \in Z}\)

I to po podstwieniu to układu początkowego już się zgadza. Ale mimo, że wyniki się zgadzają, czy metoda jest dobra? Czasem zdarza się tak, że mimo użycia złego algorytmu, wyniki otrzymuje się dobre, więc chciałbym poprosić kogoś o sprawdzenie i komentarz. Czy są szybsze, albo bardziej "eleganckie" sposoby obliczenia takiego układu?

[niuka_25]

Moim zdaniem ten układ nie ma rozwiązania. Nawet jeśli w miejce x podstawisz najmniejsze z możliwych rozwiązań tzn. 100 to już ta liczba nie będzie spełniała pierwszej z kongruencji, gdyż 9 nie dzieli (100-7).

[Mariusz M]

\(\displaystyle{ \begin{cases}
x\equiv 2 (mod \ 14)\\
x\equiv 16 (mod \ 21)\\
x\equiv 10 (mod \ 30)\\
\end{cases}}\)

Ten układ kongruencji można rozwiązać za pomocą
chińskiego twierdzenia o resztach

Moduły nie są parami względnie pierwsze więc rozbijamy ten układ
i sprawdzamy czy będziemy mogli jakieś kongruencje wykreślić

\(\displaystyle{ \begin{cases}
x\equiv 0 (mod \ 2)\\
x\equiv 2 (mod \ 7)\\
x\equiv 1 (mod \ 3)\\
x\equiv 2 (mod \ 7)\\
x\equiv 0 (mod \ 2)\\
x\equiv 1 (mod \ 3)\\
x\equiv 0 (mod \ 5)\\
\end{cases}}\)

Wykreślamy powtarzające się kongruencje


\(\displaystyle{ \begin{cases}
x\equiv 0 (mod \ 2)\\
x\equiv 2 (mod \ 7)\\
x\equiv 1 (mod \ 3)\\
x\equiv 0 (mod \ 5)\\
\end{cases}}\)

Teraz korzystamy z chińskiego twierdzenia o resztach

\(\displaystyle{ \begin{cases}
x\equiv 2 (mod \ 14)\\
x\equiv 10 (mod \ 15)\\
\end{cases}}\)

\(\displaystyle{ \begin{cases}
x\equiv 100 (mod \ 210)\\
\end{cases}}\)

Obliczając układ kongruencji za pomocą chińskiego twierdzenia o resztach
bierzemy dwie kongruencje i obliczamy największy wspólny dzielnik z rozszerzonego
algorytmu Euklidesa
(stosujemy go głównie do obliczenia kombinacji liniowej modułów gdyż z założenia wiemy że
największy wspólny dzielnik tych modułów wynosi jeden)

Do kombinacji liniowej domnażamy liczby "na krzyż"

Pierwszego układu kongruencji nie obliczysz korzystając z chińskiego twierdzenia o resztach
ale jak już Sylwek napisał widać sprzeczność

Ponieważ po rozbiciu tego układu na większą ilość kongruencji nadal moduły
nie będą względnie pierwsze (dziewiątka jest potęgą trójki)