Chinesischer Restsatz < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 22:26 Di 20.11.2007 | | Autor: | Elbi |
| Aufgabe | Lösen Sie das folgende Kongruenzensystem:
[mm]x\equiv16(mod20), x\equiv12(mod24), x\equiv8(mod28)[/mm] |
Hallo,
also ich habe ja zum Lösen von solchen Kongruenzensystemen den Chinesischen Restsatz. Das Problem hierbei ist ja aber, dass bsp.weise der [mm]ggT(24*28,20)=ggT(672,20)\not= 1[/mm] und ich den Satz ja nicht erfolgreich anwenden kann.
Ich hab' aber mal etwas probiert und kam dann dahin einfach das Kongruenzsystem folgendermaßen aufzufassen:
[mm]x\equiv16(mod20), x\equiv12(mod24), x\equiv8(mod28)[/mm]
[mm]\gdw[/mm]
[mm]x\equiv2*2*2*2(mod2*2*5), x\equiv2*2*3(mod2*2*2*3), x\equiv2*2*2(mod2*2*7)[/mm]
Wenn ich nun mit
[mm]x\equiv2(mod5), x\equiv2(mod3), x\equiv2(mod7)[/mm]
und dem Chinesischen Restsatz arbeite und anschließend:
[mm]x\equiv16*21+12*(-35)+8*15 (mod20*24*28)=36(mod13440)[/mm]
die Faktoren mit einrechne, komme ich auf eine Lösung. Mein Problem ist aber jetzt eine schlüssige Erklärung zu finden, warum ich das gerade so machen darf. Könnte mir vielleicht jemand helfen?
Vielen Dank im voraus
LG
Elbi
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 22:52 Do 22.11.2007 | | Autor: | rainerS |
Hallo!
> Lösen Sie das folgende Kongruenzensystem:
> [mm]x\equiv16(mod20), x\equiv12(mod24), x\equiv8(mod28)[/mm]
> Hallo,
>
> also ich habe ja zum Lösen von solchen Kongruenzensystemen
> den Chinesischen Restsatz. Das Problem hierbei ist ja aber,
> dass bsp.weise der [mm]ggT(24*28,20)=ggT(672,20)\not= 1[/mm] und ich
> den Satz ja nicht erfolgreich anwenden kann.
Doch, das geht schon: schau mal ![[]](/images/popup.gif) hier
> Ich hab' aber mal etwas probiert und kam dann dahin
> einfach das Kongruenzsystem folgendermaßen aufzufassen:
> [mm]x\equiv16(mod20), x\equiv12(mod24), x\equiv8(mod28)[/mm]
> [mm]\gdw[/mm]
> [mm]x\equiv2*2*2*2(mod2*2*5), x\equiv2*2*3(mod2*2*2*3), x\equiv2*2*2(mod2*2*7)[/mm]
>
> Wenn ich nun mit
> [mm]x\equiv2(mod5), x\equiv2(mod3), x\equiv2(mod7)[/mm]
> und dem
> Chinesischen Restsatz arbeite und anschließend:
> [mm]x\equiv16*21+12*(-35)+8*15 (mod20*24*28)=36(mod13440)[/mm]
> die
> Faktoren mit einrechne, komme ich auf eine Lösung. Mein
> Problem ist aber jetzt eine schlüssige Erklärung zu finden,
> warum ich das gerade so machen darf. Könnte mir vielleicht
> jemand helfen?
Die Aussage [mm]x\equiv16 \pmod{20}[/mm] ist doch äquivalent zu: [mm]x-16[/mm] ist durch 20 teilbar, und das ist äquivalent zu: [mm]x-16[/mm] ist durch 4 teilbar und [mm]x-16[/mm] ist durch 5 teilbar. Das geht, weil 4 und 5 teilerfremd sind. Allgemein gilt:
[mm]a\equiv b\pmod{m_1} [/mm] und [mm] a\equiv b\pmod{m_2} [/mm]
ist äquivalent zu
[mm]a\equiv b\pmod{\mathop{\mathrm{kgV(m_1,m_2)}}}[/mm]
Damit kannst du deine drei Kongruenzen in andere Kongruenzen umformen, zum Beispiel:
[mm]x\equiv8\pmod{28} \gdw x\equiv 8\pmod{4} \wedge x\equiv 8\pmod{7} \gdw x\equiv 0\pmod{4} \wedge x\equiv 1\pmod{7} [/mm].
Viele Grüße
Rainer
|
|
|
|
