\begin{array}{l}{\text { Bestimmen Sie mithilfe des chinesischen Restsatzes alle } x \in \mathbb{Z} \text { mit: }} \\ {\begin{array}{l}{\text { a) } x \equiv 10 \quad \text { mod } 15, \text { und } x \equiv 12 \quad \bmod 19 \text { und } x \equiv 20 \quad \bmod 28} \\ {\text { b) } x \equiv 20 \quad \bmod 23, \text { und } x \equiv 20 \quad \bmod 31 \text { und } x \equiv 20 \quad \bmod 37}\end{array}}\end{array}
Problem/Ansatz:
Ich habe es mit folgendem Algorithmus aus einem Online einsehbaren Script probiert:
\(\begin{array}{l}{\text { Konstruktion der Lösung: }} \\ {\qquad \begin{array}{l}{ \text { 1. Für }\left.1 \leq k \leq n: M_{k}:=\frac{m}{m_{k}}, N_{k}:=\operatorname{inv}_{m_{k}}\left(M_{k}\right) \text { (siehe Remark } 2.8\right)} \\ {\text { 2. } x^{\prime}:=\sum_{k=1}^{n} a_{k} M_{k} N_{k}} \\ {\text { 3. } x=\text { Rest der Division von } x^{\prime} \text { durch } m .}\end{array}}\end{array}\)
Dabei kam ich auf
\(m=15\cdot 18 \cdot 28 = 7980\)
\(M_1 =\frac{7980}{15}=532 \equiv 7 \bmod 15, \quad N_1=7 \)
\(M_2 =\frac{7980}{19}=420 \equiv 2 \bmod 19, \quad N_2=2 \)
\(M_3 = \frac{7980}{28}=285 \equiv 5 \bmod 28, \quad N_3=5\)
\(x'= 10\cdot 532 \cdot 7+12 \cdot 420 \cdot 2 + 20 \cdot 285 \cdot 5= 75820\)
\(x=75820 \equiv 4000 \bmod 7980 \) aber dieses x hat trotzdem nicht die gewünschten Reste für mod 15,19,28. Was habe ich falsch gemacht?
Außerdem hatte ich es noch mithilfe von Matrizen probiert (euklidischer Algorithmus):
\(\left( \begin{array} { l l l | l } { 1 } & { 0 } & { 0 } & { 15 } \\ { 0 } & { 1 } & { 0 } & { 19 } \\ { 0 } & { 0 } & { 1 } & { 28 } \end{array} \right)\iff\left( \begin{array} { c c c | c } { 1 } & { 0 } & { 0 } & { 15 } \\ { 0 } & { 1 } & { 0 } & { 19 } \\ { - 2 } & { 0 } & { 1 } & { - 2 } \end{array} \right)\iff \dots \iff \left( \begin{array} { c c c | c } { - 299 } & { 15 } & { 150 } & { 0 } \\ { + 20 } & { - 1 } & { - 10 } & { 1 } \\ { 38 } & { - 2 } & { - 19 } & { 0 } \end{array} \right)\)
und dann sollte man laut Vorlesung dort mithilfe der Zeile, wo die 1 im Ergebnis steht weiterrechnen, aber das habe ich nicht ganz verstanden gehabt.
Also wie ihr seht, habe ich Schwierigkeiten, den chin. Restsatz anzuwenden und würde mich über Hilfe freuen.
