Anwendung chinesischer Rests. < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 18:42 Mo 28.05.2007 | | Autor: | LenaFre |
| Aufgabe | Gesucht kleinste positive Lösung des Systems von Kongruenzen:
[mm] x\equiv1+5(mod37)
[/mm]
[mm] x\equiv16+5(mod31) [/mm] |
Hallo!
Ich hab leider nicht verstanden, wie ich den chinesischen Restsatz anwenden kann. Ich hoffe ihr könnt mir weiterhelfen.
Vielen Dank
|
|
| |
|
Hi LenaFre....
Also bei dem Chinesischen Restesatz geht es ja im Grunde darum alle Lösungen von z. B. solchen Kongruenzen wie diese zu bekommen. [mm] x\equiv1+5(mod37) [/mm]
[mm] x\equiv16+5(mod31) [/mm]
[mm] \gdw
[/mm]
[mm] x\equiv6(mod37) [/mm]
[mm] x\equiv21(mod31) [/mm]
D.h. gesucht werden alle x, die beide Kongruenzen erfüllen. Das x soll also bei Division durch 37 den Rest 6 lassen und bei Division durch 31 den Rest 21.
Nun, ich würde folgendermaßen vorgehen:
Zunächst schreibe ich eine der Kongruenzen etwas um und sage: [mm] x\equiv6(mod37) \Rightarrow [/mm] x=k*37+6. Nun setzte ich dieses x in [mm] x\equiv21(mod31) [/mm] ein und erhalte [mm] k*37+6\equiv21(mod31).
[/mm]
Das löse ich dann nach k und erhalte [mm] k\equiv18(mod31).
[/mm]
Das k, was ich gesucht habe lässt bei Division durch 31 den Rest 18. Ich wähle mir jetzt also ein k aus dieser Restklasse, z.B. die 18 selbst, denn 18 lässt bei Division durch 31 den Rest 18. dieses k setzte ich nun in die oben erwähnte Gleichung x=k*37+6 ein und bekomme eine Lösung x=672. Das ist die Kleinste positive Lösung, die die Voraussetzungen erfüllt. Nun, bei dir ist auch nur danach gefragt, aber dennoch:
Die restlichen Lösungen für x bekommst du, indem du nun 37*31 nimmst, was 1147 ergibt. D.h. nämlich, dass die Komplette Lösung "Restklasse 672 modulo 1147" lautet. Damit sind alle Lösungen angegeben. Das nächstgrößere x, das die beiden Kongruenzen erfüllt ist demnach 672+1147=1819 und das nöchstkleinere x wäre 672-1147=-475. In deiner Aufgabe fragt man jedoch nach einer kleinster positiven Lösung für x und sie ist x=672.
Nun, ich hoffe es ist dir einleutender geworden und das bring dich weiter.
MFG
|
|
|
|
