0 Daumen
1,1k Aufrufe

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

Avatar von 2,1 k

1 Antwort

+1 Daumen
 
Beste Antwort

Der Fehler liegt in deinem x ' .

x′=10⋅532⋅7+12⋅420⋅2+20⋅285⋅5=75820

Du musst von der 7 und der 2 und der 5 jeweils noch die Inversen bzgl des

jeweiligen Moduls bilden, das gibt dann 13 und 10 und 11 und damit

x′=10⋅532⋅13+12⋅420⋅10+20⋅285⋅11=182260 das ist mod 7980 dann 6700.

Und das ist in der Tat das gesuchte x.

Avatar von 289 k 🚀

Danke dir! Jetzt hab ich's verstanden.

Ist es nicht 13,10 und 17?

Ist es nicht 13,10 und 17?

Da hast du recht. Hatte mich bei dem letzten verrechnet.

Bei der 6700 klappt auch die letzte Probe nicht.

Es ist also x′=10⋅532⋅13+12⋅420⋅10+20⋅285⋅17=182260

Modulo 7980 ist das glatt 1000.

Probe:

1000 mod 15 = 10

1000 mod 19 = 12

1000 mod 28 = 20

Jetzt stimmt es !

Ein anderes Problem?

Stell deine Frage

Ähnliche Fragen

1 Antwort
0 Antworten
1 Antwort
2 Antworten
Gefragt 13 Jul 2019 von RainerWinkler
1 Antwort

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community