euklidischer algorithmus < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 23:04 Fr 08.09.2006 | | Autor: | Nessa81 |
| Aufgabe | | 912x+703y=ggT(912,703)=19 |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Hallo!
Ich will die Aufgabe 912x+703y lösen. Dazu habe ich schon den ggT(912,703)=19 berechnet und auch rückwärts wieder eingesetzt.
209=912-1*703
76=703-3*209=4*703-3*912
57=209-2*76=7*912-9*703
19=76-1*57=-10*912+13*703
Wie erhalte ich x=-10 und y=13 beim Lösen des euklidischen Algorithmus? Ich kann nicht nachvollziehen, wie die Multiplikanden jeweils nach dem 2. Gleichheitszeichen entstehen.
Ich habe schon stundenlang versuch die Rechenschritte nachzuvollziehen. Es ist mir aber leider nicht gelungen.
Ich hoffe, es kann mir einer helfen.
MfG Nessa81
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 09:34 Sa 09.09.2006 | | Autor: | felixf |
Hallo Nessa81!
> 912x+703y=ggT(912,703)=19
> Ich habe diese Frage in keinem Forum auf anderen
> Internetseiten gestellt.
>
> Hallo!
>
> Ich will die Aufgabe 912x+703y lösen. Dazu habe ich schon
> den ggT(912,703)=19 berechnet und auch rückwärts wieder
> eingesetzt.
>
> 209=912-1*703
> 76=703-3*209=4*703-3*912
> 57=209-2*76=7*912-9*703
> 19=76-1*57=-10*912+13*703
>
> Wie erhalte ich x=-10 und y=13 beim Lösen des euklidischen
> Algorithmus? Ich kann nicht nachvollziehen, wie die
> Multiplikanden jeweils nach dem 2. Gleichheitszeichen
> entstehen.
Du hast das oben also nicht selber gerechnet, sondern irgendwo vorgefunden? Andernfalls wuesstest du, wie du auf die Faktoren gekommen bist.
Du brauchst die Zwischenschritte aus dem euklidischen Algorithmus. Da rechnest du ja die ganze Zeit Division mit Rest aus, etwa $912 = 1 [mm] \cdot [/mm] 703 + 209$, und dann als naechstes $703 = q [mm] \cdot [/mm] 209 + r$, etc. Und dann faengst du auf, das rueckwaerts ineinander einzusetzen. Mal angenommen, dass du schon eine Glecihung $19 = x' [mm] \cdot [/mm] 703 + y' [mm] \cdot [/mm] 209$ hast.
Dann ersetzt du 209 durch $912 - 1 [mm] \cdot [/mm] 703$ und bekommst $19 = x' [mm] \cdot [/mm] 703 + y' [mm] \cdot [/mm] (912 - 1 [mm] \cdot [/mm] 703) = (x' - 1) [mm] \cdot [/mm] 703 + y' [mm] \cdot [/mm] 912$. Damit hast du jetzt Koeffizienten fuer 703 und 912 aus den Koeffizienten von 703 und 209 bekommen.
Fuer die anderen Schritte aus dem euklidischen Algorithmus geht das ganze genauso, nur das du mit anderen Zahlen anfaengst.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:22 Sa 09.09.2006 | | Autor: | BKM |
Hallo.
Ihre Antwort ist für mich leider im Hinblick auf die x=-10 und y= 13 nicht beantwortet. Würde mich freuen, wenn sie diese exat gestellte Frage beantworten würden.
Vielen dank.
|
|
|
| |
|
Hallo,
also nehmen wir uns mal die paar Zeilen vor. Felix hat dir das Prinzip doch erklärt und für meine Begriffe auch verständlich.
> 209=912-1*703 (**)
Ist klar! 912=1*703+209
> 76=703-3*209=4*703-3*912
Dein Problem ist das zweite Gleichheitszeichen. Du rechnest ja theoretisch erst 703=3*209+76. Das stellt man nach 76 um. Und jetzt wird das von (**) in 76=703-3*209 eingesetzt. Es folgt dann 76=703-3*(912-1*703)=4*703-3*912.
> 57=209-2*76=7*912-9*703
Hier ist es genauso. Erst euklidischer Algorithmus und dann wieder von oben einsetzen. Man nennt das übrigens auch den erweiterten euklidischen Algorithmus: 209=2*76+57 also 57=209-2*76=209-2*(4*703-3*912)=7*912-9*703
> 19=76-1*57=-10*912+13*703
Und hier genauso. So kommt man dann schlussendlich auf die Koeffizienten. Jetzt klar?
Viele Grüße
Daniel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 09:44 So 10.09.2006 | | Autor: | Nessa81 |
Hallo,
danke für eure Hilfe, ich habe vor einigen Jahren die Aufgabe schon einmal gerechnet. Daher wußte ich auch die Lösung, aber ich konnte mich nimcht mehr an den Lösungsweg erinnern. Nach einigen Stunden des Herumprobierens habe ich aber frustriert aufgegeben. Ich bin euch sehr dankbar mir geholfen zu haben.
Viele Grüße
Nessa81
|
|
|
|
