Simultane Kongruenz < Gruppe, Ring, Körper < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 12:25 Di 12.02.2013 | | Autor: | rollroll |
| Aufgabe | Hallo, ich soll folgendes Gleichungssystem lösen:
x=1 mod 108
x= 13 mod 40
x= 28 mod 225 |
Der Algorithmus ist mir eigentlich klar:
n=972000
[mm] n_1'=9000
[/mm]
[mm] n_2'=24300
[/mm]
[mm] n_3' [/mm] = 4320
[mm] ggT(n_1, n_1')=36=9000-83*108
[/mm]
[mm] ggT(n_2, n_2')=20=24300-607*40
[/mm]
[mm] ggT(n_3, n_3')=45=4320-19*225
[/mm]
x=1*9000+13*24300+28*4320=445860
Das ist allerdings falsch (wenn man die Probe macht)...
Wo ist denn mein Fehler?
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 12:32 Di 12.02.2013 | | Autor: | felixf |
Moin!
> Hallo, ich soll folgendes Gleichungssystem lösen:
> x=1 mod 108
> x= 13 mod 40
> x= 28 mod 225
> Der Algorithmus ist mir eigentlich klar:
>
> n=972000
>
> [mm]n_1'=9000[/mm]
> [mm]n_2'=24300[/mm]
> [mm]n_3'[/mm] = 4320
>
> [mm]ggT(n_1, n_1')=36=9000-83*108[/mm]
> [mm]ggT(n_2, n_2')=20=24300-607*40[/mm]
>
> [mm]ggT(n_3, n_3')=45=4320-19*225[/mm]
>
> x=1*9000+13*24300+28*4320=445860
>
> Das ist allerdings falsch (wenn man die Probe macht)...
Der Algorithmus funktioniert so nur, wenn die Moduli paarweise teilerfremd sind. Das sind sie hier aber nicht, wie du an den ggTs sehen kannst, die alle $ > 1$ sind.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 12:36 Di 12.02.2013 | | Autor: | rollroll |
Ok, danke schonmal. Und wie löst man eine solche Kongruenz, wenn die Moduli nicht teilerfremd sind?
|
|
|
| |
|
Hallo nochmal,
> Ok, danke schonmal. Und wie löst man eine solche
> Kongruenz, wenn die Moduli nicht teilerfremd sind?
Man überführt das System in eines mit teilerfremden Moduln. Siehe dazu meine Antwort weiter unten.
Grüße
reverend
|
|
|
| |
|
Hallo rollroll,
da (wie Felix ja schon schrieb) die Moduln nicht teilerfremd sind, kannst Du so vorgehen:
> Hallo, ich soll folgendes Gleichungssystem lösen:
> x=1 mod 108
> x= 13 mod 40
> x= 28 mod 225
Aus der ersten Kongruenz folgt [mm] x\equiv 1\mod{4} [/mm] und [mm] x\equiv 1\mod{27}.
[/mm]
Aus der zweiten folgt [mm] x\equiv 3\mod{5} [/mm] und [mm] x\equiv 5\mod{8}.
[/mm]
Aus der dritten folgt [mm] x\equiv 1\mod{9} [/mm] und [mm] x\equiv 3\mod{25}.
[/mm]
Diese Angaben kann man nun zusammenfassen zum neuen System
[mm] x\equiv 5\mod{8}
[/mm]
[mm] x\equiv 1\mod{27}
[/mm]
[mm] x\equiv 3\mod{25}
[/mm]
> Der Algorithmus ist mir eigentlich klar:
Den kannst Du jetzt ja noch einmal anwenden. 
Grüße
reverend
>
> n=972000
>
> [mm]n_1'=9000[/mm]
> [mm]n_2'=24300[/mm]
> [mm]n_3'[/mm] = 4320
>
> [mm]ggT(n_1, n_1')=36=9000-83*108[/mm]
> [mm]ggT(n_2, n_2')=20=24300-607*40[/mm]
>
> [mm]ggT(n_3, n_3')=45=4320-19*225[/mm]
>
> x=1*9000+13*24300+28*4320=445860
>
> Das ist allerdings falsch (wenn man die Probe macht)...
>
> Wo ist denn mein Fehler?
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 12:48 Di 12.02.2013 | | Autor: | rollroll |
Vielen Dank!
Nur noch eine Frage; Kann man statt dem neuen system, das du hingeschrieben hast, auch
x= 1 mod4
x= 3 mod5
x= 1 mod9
benutzen? Oder muss man immer die Kongruent nehemen mit der größten Zahl hinter dem Modulo?
|
|
|
| |
|
Hallo nochmal,
> Nur noch eine Frage; Kann man statt dem neuen system, das
> du hingeschrieben hast, auch
>
> x= 1 mod4
> x= 3 mod5
> x= 1 mod9
>
> benutzen?
Das ist zwar nicht falsch, reicht aber nicht aus.
Die Moduln des neuen Systems müssen das gleiche kgV haben wie die des alten.
> Oder muss man immer die Kongruent nehemen mit der
> größten Zahl hinter dem Modulo?
Ja, jeder Primfaktor muss in der höchsten auftretenden Potenz vorkommen.
Grüße
reverend
|
|
|
|
