Skracanie układu kongruencji

[remique]

Mam do rozwiązania następujący układ
\[
\left\{\begin{array}{rcl}
x&\equiv&13 \ (mod \ 13)\\
x&\equiv&9 \ (mod \ 24)\\
x&\equiv&21 \ (mod \ 60)
\end{array} \right.
\]
Aby rozwiązać ten układ korzystając z Chińskiego Twierdzenia o Resztach, trzeba go sprowadzić do takiego, gdzie liczby modulo są względnie pierwsze. Jak pojmuję - powinienem się pozbyć informacji, które są już zawarte w układach o wyższych liczbach modulo.

Problem w tym, że w momencie gdy to robię wynik wychodzi mi zły, tj. \(240\cdot k + 141 \ , \ k \in \zz \). Wynik ten działa dla \((mod \ 13)\) oraz \((mod \ 60)\), ale nie dla \((mod \ 24)\).

Czy ktoś byłby tak miły i pokazał jak powinenem przekształcić ten układ do takiego, gdzie mogę skorzystać z CRT?

[kerajs]

Problem w tym, że w momencie gdy to robię wynik wychodzi mi zły, tj. \(240\cdot k + 141 \ , \ k \in \zz \). Wynik ten działa dla \((mod \ 13)\) oraz \((mod \ 60)\),

Ten wynik nie działa już dla \(mod \ 13\)

Zacznę od ostatniego równania:
\(x=60a+21=48a+12a+21\)
Dla parzystego a wyznaczony x nie spełnia drugiego równania gdyż \(x \ mod \ 24=21 \neq 9\)
Sprawdzam nieparzyste a:
\(x=60(2b+1)+21=120b+81=24 \cdot (5b+3)+9\)
(Gdyby i teraz \(x \ mod \ 24 \neq 9\) to układ byłby sprzeczny.)
Pozostaje pierwszy warunek:
\(x \ mod \ 13=0\)
więc
\(x= 120b+81=120(13c+k)+13 \cdot 6+3=13(120c+9k+6)+3(k+1)\)
Łatwo zauważyć iż \(k=12\) , a stąd rozwiązanie \(x=1560c+1521\)

[remique]

Dzięki za szybką odpowiedź.

Generalnie widzę że popełniłem literówkę przy przepisywaniu układu. Zamiast \((mod \ 13)\) powinno być \((mod \ 16)\), tj:
\[
\left\{\begin{array}{rcl}
x&\equiv&13 \ (mod \ 16)\\
x&\equiv&9 \ (mod \ 24)\\
x&\equiv&21 \ (mod \ 60)
\end{array} \right.
\]
Próbowałem rozwiązać to twoją metodą i wychodzi mi \(8 \cdot b \equiv 4 \ (mod \ 16)\) co oczywiście nie ma rozwiązań.
Opiszę swoją metodę rozwiązywania takiego układu poniżej i może będziesz w stanie mi pokazać gdzie robie błąd.

Rozkładam odpowiednio 16, 24 i 60 na czynniki. \( 16 = 2^{4} \ , \ 24 = 2^{3} \cdot 3 \ , \ 60 = 2^{2} \cdot 3 \cdot 5\). Teraz powyższy układ kongruencji mogę zapisać jako:
\[
\left\{\begin{array}{rcl}
x&\equiv&13 \ (mod \ 16) \\
x&\equiv&9 \ (mod \ 24) \\
x&\equiv&21 \ (mod \ 60)
\end{array} \right.

\iff

\left\{\begin{array}{rcl}
x&\equiv&13 \ (mod \ 2^{4}) \\
x&\equiv&9 \ (mod \ 2^{3}) \\
x&\equiv&9 \ (mod \ 3) \\
x&\equiv&21 \ (mod \ 2^{2}) \\
x&\equiv&21 \ (mod \ 3) \\
x&\equiv&21 \ (mod \ 5)
\end{array} \right.
\]

Aby nie stracić żadnej informacji kluczowej dla rozwiązania, muszę zostawić najwyższe potęgi tych liczb pierwszych, natomiast mogę wyrzucić z tego układu niższe potęgi jako, że są równoważne (np. \(x\equiv 13 \ (mod \ 2^{4}) \iff x\equiv 9 \ (mod \ 2^{3}) \iff x\equiv 1 \ (mod \ 2)\)). Oczywiście zakładając, że układ jest niesprzeczny.

Z tego względu pozbywam się z układu \(x\equiv 9 \ (mod \ 2^{3})\), \(x\equiv 21 \ (mod \ 2^{2})\) oraz \(x\equiv 21 \ (mod \ 3)\). W moim układzie zostają więc:
\[
\left\{\begin{array}{rcl}
x&\equiv&13 \ (mod \ 16) \\
x&\equiv&9 \ (mod \ 3) \\
x&\equiv&21 \ (mod \ 5)
\end{array} \right.

\iff

\left\{\begin{array}{rcl}
x&\equiv&13 \ (mod \ 16) \\
x&\equiv&0 \ (mod \ 3) \\
x&\equiv&1 \ (mod \ 5)
\end{array} \right.
\]

Gdzie mogę już zastosować CRT, jednak sprawdzając wynik rozwiązania takiego układu z pierwotnym wychodzą zupełne głupoty. Może układ jest tak naprawdę sprzeczny a ja tego nie widzę?

[kerajs]

Próbowałem rozwiązać to twoją metodą i wychodzi mi \(8 \cdot b \equiv 4 \ (mod \ 16)\) co oczywiście nie ma rozwiązań.

Mi wychodzi ciut inaczej:
\((120b+81) \ mod \ 16 \equiv (8\cdot b +1) mod \ 16 \)
co dla parzystych b daje resztę 1, a dla nieparzystych b resztę 9. W obu przypadkach nie jest to 13 więc układ jest sprzeczny.

\[
\left\{\begin{array}{rcl}
x&\equiv&13 \ (mod \ 2^{4}) \\
x&\equiv&9 \ (mod \ 2^{3}) \\
x&\equiv&9 \ (mod \ 3) \\
x&\equiv&21 \ (mod \ 2^{2}) \\
x&\equiv&21 \ (mod \ 3) \\
x&\equiv&21 \ (mod \ 5)
\end{array} \right.
\]

co po uproszczeniu daje
\[
\left\{\begin{array}{rcl}
x&\equiv&13 \ (mod \ 2^{4}) \\
x&\equiv&1 \ (mod \ 2^{3}) \\
x&\equiv&0 \ (mod \ 3) \\
x&\equiv&1 \ (mod \ 2^{2}) \\
x&\equiv&0 \ (mod \ 3) \\
x&\equiv&1 \ (mod \ 5)
\end{array} \right.
\]
W pierwszym równaniu układu masz \(x \ \equiv \ 13 \ (mod \ 2^{4}) \) co oznacza iż \(x \ \equiv \ 5 \ (mod \ 2^{3}) \) , a to jest sprzeczne z równaniem drugim, więc i cały układ jest sprzeczny.

A błąd jest tutaj:

Aby nie stracić żadnej informacji kluczowej dla rozwiązania, muszę zostawić najwyższe potęgi tych liczb pierwszych, natomiast mogę wyrzucić z tego układu niższe potęgi jako, że są równoważne (np. \(x\equiv 13 \ (mod \ 2^{4}) \iff x\equiv 9 \ (mod \ 2^{3}) \iff x\equiv 1 \ (mod \ 2)\)). Oczywiście zakładając, że układ jest niesprzeczny.

Przy błędnym założeniu pozbyłeś się równania które wskazuje na sprzeczność układu.
Przy okazji, w tej (pomijam że nieprawdziwej) tezie:
\(x\equiv 13 \ (mod \ 2^{4}) \iff x\equiv 9 \ (mod \ 2^{3}) \iff x\equiv 1 \ (mod \ 2)\) mogą być jedynie implikacje (w prawo), a nie równoważności.