Chin. Restsatz

30.12.2008, 18:47

BrettvormKopp

Chin. Restsatz

Hallo,
ich brauche mal Hilfe bei dieser Aufgabe, ich soll das Kongruenzsystem lösen
$\begin{eqnarray*} x\equiv 1 mod 2 <br /> x\equiv 0 mod 3 <br /> x\equiv 3 mod 7 <br /> x\equiv 8 mod 11<br /> mit x \leq 500 \end{eqnarray*}$
Da ggt(2,3,7,11)=1 kann ich ja den chin. Restsatz anwenden.
Gehe ich nach Wiki vor, dann ist $\begin{eqnarray*} M=2*3*7*11=462 \end{eqnarray*}$ und somit $\begin{eqnarray*} M_1=231, M_2=154, M_3=66, M_4=42 \end{eqnarray*}$
$\begin{eqnarray*} ggT(M_i)=1 \end{eqnarray*}$
nur jetzt hakt es bei mir. Wie komm ich weiter?

30.12.2008, 19:49

Reksilat

Auf diesen Beitrag antworten »

RE: Chin. Restsatz
Es ist $\begin{eqnarray*} {\rm ggT}(m_i,M_i)=1 \end{eqnarray*}$ , also gibt es $\begin{eqnarray*} r_i \end{eqnarray*}$ und $\begin{eqnarray*} s_i \end{eqnarray*}$ , mit $\begin{eqnarray*} r_im_i+s_iM_i=1 \end{eqnarray*}$ . Für $\begin{eqnarray*} i=1 \end{eqnarray*}$ gilt beispielsweise $\begin{eqnarray*} 116\cdot2+(-1)\cdot 231=1 \end{eqnarray*}$ .
Nun weiter für $\begin{eqnarray*} i=2,3,4 \end{eqnarray*}$ .

Tipp: Nimm für jede Zeile einen eigenen Latex-Tag, da sonst das passiert, was in Deinem Posting zu sehen ist.

02.01.2009, 18:23

BrettvormKopp

Auf diesen Beitrag antworten »

Erstmal danke. Eigentlich hatte ich in jeder Zeile nen neuen Code...
Dass ich so weitermache, war mir auch klar (hätte ich vlt auch schreiben sollen Augenzwinkern

).
Die Frage ist nur wie komm ich darauf? Nur durch ausprobrieren?

02.01.2009, 19:28

Reksilat

Auf diesen Beitrag antworten »

Zitat:

Die Frage ist nur wie komm ich darauf? Nur durch ausprobrieren?

Meinst Du die Bestimmung der $\begin{eqnarray*} r_i \end{eqnarray*}$ und $\begin{eqnarray*} s_i \end{eqnarray*}$ ? Das macht man mit dem euklidischen Algorithmus oder bei kleineren Zahlen gern auch mal durch Probieren (geht zumeist schneller).

03.01.2009, 21:24

BrettvormKopp

Auf diesen Beitrag antworten »

RE: Chin. Restsatz
Für $\begin{eqnarray*} i=2 \end{eqnarray*}$ gilt dann $\begin{eqnarray*} -51\cdot3+1\cdot 154=1 \end{eqnarray*}$ .
Für $\begin{eqnarray*} i=3 \end{eqnarray*}$ gilt dann $\begin{eqnarray*} 19\cdot7+(-2)\cdot 66=1 \end{eqnarray*}$ .
Nur für i=4 bekomm ich gerade nichts raus. Kann mir wer helfen?

03.01.2009, 21:55

BrettvormKopp

Auf diesen Beitrag antworten »

RE: Chin. Restsatz
[quote]Original von BrettvormKopp
Für $\begin{eqnarray*} i=2 \end{eqnarray*}$ gilt dann $\begin{eqnarray*} -51\cdot3+1\cdot 154=1 \end{eqnarray*}$ .
Für $\begin{eqnarray*} i=3 \end{eqnarray*}$ gilt dann $\begin{eqnarray*} 19\cdot7+(-2)\cdot 66=1 \end{eqnarray*}$ .
Für $\begin{eqnarray*} i=4 \end{eqnarray*}$ gilt dann $\begin{eqnarray*} -61\cdot11+16\cdot 42=1 \end{eqnarray*}$ .
Hab ich nun.
Dann gilt: $\begin{eqnarray*} e_1=-231 \end{eqnarray*}$
$\begin{eqnarray*} e_2=154 \end{eqnarray*}$
$\begin{eqnarray*} e_3=-132 \end{eqnarray*}$
$\begin{eqnarray*} e_4=672 \end{eqnarray*}$
Dann müsste doch $\begin{eqnarray*} x=1\cdot(-231)+0\cdot154+3\cdot(-132)+8\cdot672=4749 \end{eqnarray*}$ sein.
Was hab ich falsch gemacht? Wäre schon, wenn mir jemand helfen könnte. x soll doch kleiner 500 sein...

04.01.2009, 00:54

Reksilat

Auf diesen Beitrag antworten »

RE: Chin. Restsatz
Du hast nichts falsch gemacht, aber der Algorithmus findet nunmal nicht die minimale Lösung. Wenn Du den Wert x=4749 um 2*3*7*11=462 abänderst, veränderst Du die Kongruenzen nicht und somit ist $\begin{eqnarray*} x=4749+k\cdot 462 \end{eqnarray*}$ für alle k eine Lösung der Kongruenzen. Für ein passendes k ist dann auch x<500.

Neue Frage »

Antworten »

Chin. Restsatz

Verwandte Themen