Chinesischer Restsatz < Sonstiges < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:09 Fr 28.11.2008 | | Autor: | Firecrow |
| Aufgabe | Bestimmen ie das kleinste n [mm] \in \IN [/mm] mit
n [mm] \equiv [/mm] 3 mod 10 [mm] \wedge [/mm] n [mm] \equiv [/mm] 4 mod 13 [mm] \wedge [/mm] n [mm] \equiv [/mm] 5 mod 21. |
Hier benutze ich den Chinesischen Restsatz zur Berechnung.
Heraus habe ich schon
M1 = 273, M2 = 210, M3 = 130
Jetzt komm ich aber bei der linearen Darstellung des ggT(273, 210, 130) nicht weiter
Der ggT(273, 210) = 21 = 4*210-3*273
ggT(130, 21) = 1 = 31*21-5*130
Die lineare Darstellung müsste dann folgendermassen aussehen:
ggT(273, 210, 130) = 1 = -3*273+4*210-5*130 , aber wie ihr feststellt ist diese Gleichung [mm] \not= [/mm] 1
Hab ich da irgendwo einen Fehler gemacht, oder geht die Rechnung nich auf und es gibt kein kleinstes n??
Gruss Fire
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:21 Fr 28.11.2008 | | Autor: | glie |
Hallo,
verzeih bitte meine Unkenntnis des chinesischen Restsatzes, aber die Lösung ist n=173 (herausgefunden durch Tabellenkalkulation)....
also zumindest gibt es eine Lösung!
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 16:43 Fr 28.11.2008 | | Autor: | Firecrow |
Hier einmal eine Erklärung, des CHinesischen Restsatzes. ;)
http://de.wikipedia.org/wiki/Chinesischer_Restsatz
Ok. Das Ergebnis hab ich schon einmal, nur hilft mir das leider nicht bei meinem Problem weiter.
Danke trotzdem. :)
|
|
|
| |
|
Hallo FireCrow,
> Bestimmen ie das kleinste n [mm]\in \IN[/mm] mit
> n [mm]\equiv[/mm] 3 mod 10 [mm]\wedge[/mm] n [mm]\equiv[/mm] 4 mod 13 [mm]\wedge[/mm] n [mm]\equiv[/mm]
> 5 mod 21.
> Hier benutze ich den Chinesischen Restsatz zur
> Berechnung.
> Heraus habe ich schon
> M1 = 273, M2 = 210, M3 = 130
>
> Jetzt komm ich aber bei der linearen Darstellung des
> ggT(273, 210, 130) nicht weiter
> Der ggT(273, 210) = 21 = 4*210-3*273
> ggT(130, 21) = 1 = 31*21-5*130
>
> Die lineare Darstellung müsste dann folgendermassen
> aussehen:
> ggT(273, 210, 130) = 1 = -3*273+4*210-5*130 , aber wie ihr
> feststellt ist diese Gleichung [mm]\not=[/mm] 1
>
> Hab ich da irgendwo einen Fehler gemacht, oder geht die
> Rechnung nich auf und es gibt kein kleinstes n??
Bei der Lösung von simultanen Kongruenzen wird folgendermaßen vorgegangen:
Ermittle zunächst, die Koeffizienten der folgenden Darstellungen mit Hilfe des ![[]](/images/popup.gif) erweiterten euklidischen Algorithmus:
[mm]s_{1}*m_{1}+r_{1}*M_{1}=1[/mm]
[mm]s_{2}*m_{2}+r_{2}*M_{2}=1[/mm]
[mm]s_{3}*m_{3}+r_{3}*M_{3}=1[/mm]
mit [mm]m_{i}*M_{i}=M[/mm]
Hier also:
[mm]s_{1}*10+r_{1}*273=1[/mm]
[mm]s_{2}*13+r_{2}*210=1[/mm]
[mm]s_{3}*21+r_{3}*130=1[/mm]
Dann ist eine Lösung der simultanen Kongruenz gegeben durch
[mm]x=a_{1}*\left(r_{1}*M_{1}\right)+a_{2}*\left(r_{2}*M_{2}\right)+a_{3}*\left(r_{3}*M_{3}\right)[/mm]
Hier bedeutet das:
[mm]x=3*\left(r_{1}*273\right)+4*\left(r_{2}*210\right)+5*\left(r_{3}*130\right)[/mm]
Siehe auch: Chinesischer Restsatz
>
> Gruss Fire
Gruß
MathePower
|
|
|
|
