Lemma von Bezout(Gleichung lös < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
Status: |
(Frage) beantwortet | Datum: | 06:09 Di 03.11.2009 | Autor: | SUNNY000 |
Aufgabe | Finde alle Lösungen x,y [mm] \in [/mm] Z , so dass die folgende Gleichung gilt:
-15x+110y=50 |
Hallo liebe Community,
ich habe eine kleine verständnisfrage. Sitze nun an meinem skript und komme nicht weiter. Liege ich da richtig, wenn ich sage, dass ich hier das Lemma von Bezout anwenden muss? Ich hätte zuerst den ggT bestimmt, also ggT=(-15,110)=5. Die Gleichung könnte ich im Prinzip durch 5 teilen und somit kürzen. Und evtl. nach x umstellen: [mm] x=\bruch{22y-10}{3}. [/mm] Mir schwebt noch irgendwie [mm] 22y\equiv [/mm] 10(mod 3), indem ich die Gleichung nach y umforme, dennoch weiß ich nihct, was ich damit anfangen kann. Aber was mache ich weiter, wie gehe ich dann vor?
Lieben dank im voraus
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
|
|
> Finde alle Lösungen x,y [mm]\in[/mm] Z , so dass die folgende
> Gleichung gilt:
> -15x+110y=50
> Hallo liebe Community,
>
> ich habe eine kleine verständnisfrage. Sitze nun an meinem
> skript und komme nicht weiter. Liege ich da richtig, wenn
> ich sage, dass ich hier das Lemma von Bezout anwenden muss?
> Ich hätte zuerst den ggT bestimmt, also ggT=(-15,110)=5.
> Die Gleichung könnte ich im Prinzip durch 5 teilen und
> somit kürzen.
Hallo,
dann hast Du -3x+22y=10.
Der ggT(3,22)=1.
Also findest Du (Bezout) [mm] r,s\in \IZ [/mm] mit -3r+22s=1.
Bestimme also r,s. (erweiterter euklidischer Algorithmus.)
Damit ist dann die Hauptarbeit getan.
Gruß v. Angela
> Und evtl. nach x umstellen:
> [mm]x=\bruch{22y-10}{3}.[/mm] Mir schwebt noch irgendwie [mm]22y\equiv[/mm]
> 10(mod 3), indem ich die Gleichung nach y umforme, dennoch
> weiß ich nihct, was ich damit anfangen kann. Aber was
> mache ich weiter, wie gehe ich dann vor?
>
> Lieben dank im voraus
>
>
> Ich habe diese Frage in keinem Forum auf anderen
> Internetseiten gestellt.
|
|
|
|
|
Status: |
(Frage) beantwortet | Datum: | 15:35 Di 03.11.2009 | Autor: | SUNNY000 |
Hallo Angela,
danke dir für die Antwort.
1. Frage: wie genau kommst du auf 3r+10s=1? bzw. nach welcher formel stellst du die gleichung so auf, dass die 22 wegfällt?
2.Frage: wenn ich die Gleichung mit dem erweiterten euklidischen Algorithmus lösen möchte, muss ich diese dementsprechend umstellen. Wäre es so richtig? 3r [mm] \equiv [/mm] 1(mod 22)?
An den erweiterten euklidischen Algorithmus habe ich auch shcon gedacht, aber am Ende habe ich doch nur die Linearkombination raus, wenn die Frage aber lautet, "Finde alle Lösungen x,y". Wie komme ich dadurch auf ALLE Lösungen?
LG
Sunny
|
|
|
|
|
Status: |
(Mitteilung) Reaktion unnötig | Datum: | 16:11 Di 03.11.2009 | Autor: | Niladhoc |
Hallo,
ich bin mir unsicher, aber ist nicht, wenn [mm] y=\bruch{1}{22}*(10 [/mm] mod [mm] 3)=\bruch{1}{22}*(1 [/mm] mod 3) gilt und da [mm] y\in \IZ [/mm] auch y mod 22 [mm] \equiv [/mm] 0 gilt, jedes Zahlenpaar [mm] (\bruch{22y-10}{3},y) [/mm] eine Lösung?
y lässt sich dann mit dem chin. Restsatz bestimmen.
lg
|
|
|
|
|
Status: |
(Mitteilung) Reaktion unnötig | Datum: | 16:22 Di 03.11.2009 | Autor: | SUNNY000 |
Hallo,
leider haben wir noch nicht mit dem chin. Restsatz gearbeiten :(
|
|
|
|
|
> Hallo Angela,
>
> danke dir für die Antwort.
> 1. Frage: wie genau kommst du auf 3r+10s=1? bzw. nach
> welcher formel stellst du die gleichung so auf, dass die 22
> wegfällt?
Meine Güte!
Nach gar keiner Formel!
Entschuldigung, ich war wohl nicht bei Sinnen.
Das sollte eigentlich heißen -3r+22s=1.
Ich denke, so ist's besser verständlich. Richtiger ist's auf alle Fälle.
Ich rate jetzt mal schnell eine Lösung: r=7 und y=1.
Also ist x=70 und y=10 eine Lösung von -3x+22y=10.
Damit weiß ich, daß auch x=70+22k und y=10+3k für alle [mm] k\in \IZ [/mm] eine Lösung liefert, denn es ist
10= -3*70 +22*10=-3(70+22k) + 22*(10+3k)
Ich kann das jetzt natürlich noch "reduziert " aufschreiben:
x=70+22k=4 + 22*(3+k)=4+22k', y=10+3k=1+3*(3+k)=1+3k'
Gruß v. Angela
|
|
|
|
|
Status: |
(Antwort) fertig | Datum: | 17:38 Di 03.11.2009 | Autor: | abakus |
> Finde alle Lösungen x,y [mm]\in[/mm] Z , so dass die folgende
> Gleichung gilt:
> -15x+110y=50
> Hallo liebe Community,
>
> ich habe eine kleine verständnisfrage. Sitze nun an meinem
> skript und komme nicht weiter. Liege ich da richtig, wenn
> ich sage, dass ich hier das Lemma von Bezout anwenden muss?
> Ich hätte zuerst den ggT bestimmt, also ggT=(-15,110)=5.
> Die Gleichung könnte ich im Prinzip durch 5 teilen und
> somit kürzen. Und evtl. nach x umstellen:
> [mm]x=\bruch{22y-10}{3}.[/mm] Mir schwebt noch irgendwie [mm]22y\equiv[/mm]
> 10(mod 3), indem ich die Gleichung nach y umforme, dennoch
> weiß ich nihct, was ich damit anfangen kann. Aber was
> mache ich weiter, wie gehe ich dann vor?
>
Hallo,
es gilt die Regel
Aus [mm] a\equiv [/mm] b mod m und [mm] c\equiv [/mm] d mod m folgt [mm] a-b\equiv [/mm] c-d mod m .
Diese Regel gilt analog für Addition und Multiplikation von Kongruenzen.
Offensichtlich ist 21y-9 durch 3 teilbar, und 22y-10 soll es auch sein.
Also gilt neben
[mm]21y-9\equiv[/mm] 0(mod 3) auch
[mm]22y-10\equiv[/mm] 0(mod 3) .
Die Differenz beider Kongruenzen ergibt y-1 [mm] \equiv [/mm] 0 (mod 3).
Gruß Abakus
> Lieben dank im voraus
>
>
> Ich habe diese Frage in keinem Forum auf anderen
> Internetseiten gestellt.
|
|
|
|