System von Kongruenzen lösen < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 12:15 Mo 19.10.2015 | | Autor: | MinLi |
| Aufgabe | Lösen Sie folgendes System von Kongruenzen:
9x + 2y -3 [mm] \equiv [/mm] 6 mod 20
-3x + 7y +3 [mm] \equiv [/mm] 11 mod 20 |
Hallo,
ich soll diese Aufgabe lösen, weiß aber nicht so richtig wie.
Wir haben in der Vorlesung zu Kongruenzen den chinesischen Restsatz eingeführt, aber den kann man in der Aufgabe, so wie sie da steht, nicht verwenden, da die beiden Modulos nicht teilerfremd sind.
Ich habe versucht das System etwas umzuschreiben:
9x + 2y [mm] \equiv [/mm] 9 mod 20
-3x + 7y [mm] \equiv [/mm] 8 mod 20
und dann habe ich mir gedacht, dass man vielleicht mit Substitution weiterkommt. Also habe ich die erste Gleichung so umgeschrieben, dass man x in die zweite Gleichung einfügen kann:
x [mm] \equiv [/mm] 1 - 2/9y mod 20
-3*(1 - 2/9y) + 7y [mm] \equiv [/mm] 8 mod 20
[mm] \gdw
[/mm]
x [mm] \equiv [/mm] 1 - 2/9y mod 20
y [mm] \equiv [/mm] 33/23 mod 20
[mm] \gdw
[/mm]
x [mm] \equiv [/mm] 47/69 mod 20
y [mm] \equiv [/mm] 33/23 mod 20
Ich kann mir aber nicht vorstellen dass dies die Lösung zu dem System ist, da ich mod20 gar nicht verwendet habe und da dann die Lösung in [mm] \IZ_{20} [/mm] gleich der Lösung in [mm] \IZ [/mm] wäre und dann hätten wir diese Aufgabe bestimmt nicht als Übungsaufgabe gekriegt.
Also nun meine Frage: Wie kann man solch ein System von Kongruenzen lösen? (Bitte keine ganze Lösung, sondern nur ein paar Hilfestellungen)
Viele Grüße, MinLi
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 12:45 Mo 19.10.2015 | | Autor: | abakus |
> Lösen Sie folgendes System von Kongruenzen:
>
> 9x + 2y -3 [mm]\equiv[/mm] 6 mod 20
> -3x + 7y +3 [mm]\equiv[/mm] 11 mod 20
> Hallo,
>
> ich soll diese Aufgabe lösen, weiß aber nicht so richtig
> wie.
> Wir haben in der Vorlesung zu Kongruenzen den chinesischen
> Restsatz eingeführt, aber den kann man in der Aufgabe, so
> wie sie da steht, nicht verwenden, da die beiden Modulos
> nicht teilerfremd sind.
> Ich habe versucht das System etwas umzuschreiben:
>
> 9x + 2y [mm]\equiv[/mm] 9 mod 20
> -3x + 7y [mm]\equiv[/mm] 8 mod 20
Hallo,
aus die zweite Kongruenz könnte man verdreifachen zu
[mm] -9x+21y$\equiv$ [/mm] 24 mod 20 und dann zur ersten addieren.
Man erhält
[mm] 23y$\equiv$ [/mm] 33 mod 20 ; das entspricht dem, was du weiter unten in Bruchschreibweise hast.
Wegen [mm] 23$\equiv$ [/mm] 3 mod 20 gilt auch [mm] 23y$\equiv$ [/mm] 3y mod 20.
Man kann nun in [mm] 23y$\equiv$ [/mm] 33 mod 20 große Zahlen durch kongruente kleinere Zahlen ersetzen und bekommt
[mm] 3y$\equiv$ [/mm] 33 mod 20 ; nach Division durch 11 (Modul ändert sich wegen ggT(11,20)=1 nicht) erhält man
[mm] y$\equiv$ [/mm] 11 mod 20.
Damit folgt [mm] 2y$\equiv$ 22$\equiv$ [/mm] 2 mod 20.
Somit kann man auch noch in einer anderen Kongruenz 2y durch 2 ersetzen.
Gruß Abakus
>
> und dann habe ich mir gedacht, dass man vielleicht mit
> Substitution weiterkommt. Also habe ich die erste Gleichung
> so umgeschrieben, dass man x in die zweite Gleichung
> einfügen kann:
>
> x [mm]\equiv[/mm] 1 - 2/9y mod 20
> -3*(1 - 2/9y) + 7y [mm]\equiv[/mm] 8 mod 20
>
> [mm]\gdw[/mm]
>
> x [mm]\equiv[/mm] 1 - 2/9y mod 20
> y [mm]\equiv[/mm] 33/23 mod 20
>
> [mm]\gdw[/mm]
>
> x [mm]\equiv[/mm] 47/69 mod 20
> y [mm]\equiv[/mm] 33/23 mod 20
>
> Ich kann mir aber nicht vorstellen dass dies die Lösung zu
> dem System ist, da ich mod20 gar nicht verwendet habe und
> da dann die Lösung in [mm]\IZ_{20}[/mm] gleich der Lösung in [mm]\IZ[/mm]
> wäre und dann hätten wir diese Aufgabe bestimmt nicht als
> Übungsaufgabe gekriegt.
> Also nun meine Frage: Wie kann man solch ein System von
> Kongruenzen lösen? (Bitte keine ganze Lösung, sondern nur
> ein paar Hilfestellungen)
>
> Viele Grüße, MinLi
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 10:32 Mi 21.10.2015 | | Autor: | MinLi |
Danke für die schnelle Antwort.
Viele Grüße, MinLi
|
|
|
|
