Euklidischer Algorithmus < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
Ich möchte die diophantische Gleichung 77*x+120*y=1 per erweitertem euklidischen Algorithmus ausrechnen!
Als onlinetool habe ich http://www.mirsky.de/ggt.php gefunden, welches mir z.B. detailliert sagt wie der Zwischenschritt ggT(43, 34) entstanden ist:
43=1*120+-1*77 Erklaerung: x=sa+tb
34=-1*120+2*77 Erklaerung: y=ua+vb
Meine Frage lautet nun:
Woher weiß ich denn ob ich z.B. bei der 34,dass ich -1 als y wähle und 2 als x...
Kann mir einer dieses Zurückrechnen erklären?
Leider geht mir das nicht auf, obwohl es wahscheinlich überhaupt nicht schwer ist...
Grüße
:)
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
Hallo kunterbunt,
![[willkommenmr]](/images/smileys/willkommenmr.png "[willkommenmr]")
> Ich möchte die diophantische Gleichung 77*x+120*y=1 per
> erweitertem euklidischen Algorithmus ausrechnen!
> Als onlinetool habe ich http://www.mirsky.de/ggt.php
> gefunden, welches mir z.B. detailliert sagt wie der
> Zwischenschritt ggT(43, 34) entstanden ist:
> 43=1*120+-1*77 Erklaerung: x=sa+tb
> 34=-1*120+2*77 Erklaerung: y=ua+vb
>
> Meine Frage lautet nun:
> Woher weiß ich denn ob ich z.B. bei der 34,dass ich -1
> als y wähle und 2 als x...
>
> Kann mir einer dieses Zurückrechnen erklären?
Der erste Schritt beim euklidischen Algorithmus ist:
[mm]120=1*77+43 \gdw 43=1*120+\left(-1\right)*77[/mm]
Jetzt der zweite Schritt:
[mm]77=1*43+34 \gdw 34=1*77+\left(-1\right)*43[/mm]
Mit ersterer Gleichung folgt:
[mm]34=1*77+\left(-1\right)*\blue{43}=1*77+\left(-1\right)*\blue{\left(1*120+\left(-1\right)*77\right)}=2*77+\left(-1\right)*120[/mm]
> Leider geht mir das nicht auf, obwohl es wahscheinlich
> überhaupt nicht schwer ist...
> Grüße
> :)
>
> Ich habe diese Frage in keinem Forum auf anderen
> Internetseiten gestellt.
Gruss
MathePower
|
|
|
| |
|
> Der erste Schritt beim euklidischen Algorithmus ist:
>
> [mm]120=1*77+43 \gdw 43=1*120+\left(-1\right)*77[/mm]
>
> Jetzt der zweite Schritt:
>
> [mm]77=1*43+34 \gdw 34=1*77+\left(-1\right)*43[/mm]
>
> Mit ersterer Gleichung folgt:
>
> [mm]34=1*77+\left(-1\right)*\blue{43}=1*77+\left(-1\right)*\blue{\left(1*120+\left(-1\right)*77\right)}=2*77+\left(-1\right)*120[/mm]
>
Mir ist der 3. Schritt, also wie ich auf die "entstehung" der 34 komme absolut unklar...
|
|
|
| |
|
Hallo
> > Der erste Schritt beim euklidischen Algorithmus ist:
> >
> > [mm]120=1*77+43 \gdw 43=1*120+\left(-1\right)*77[/mm]
> >
> > Jetzt der zweite Schritt:
> >
> > [mm]77=1*43+34 \gdw 34=1*77+\left(-1\right)*43[/mm]
> >
> > Mit ersterer Gleichung folgt:
> >
> >
> [mm]34=1*77+\left(-1\right)*\blue{43}=1*77+\left(-1\right)*\blue{\left(1*120+\left(-1\right)*77\right)}=2*77+\left(-1\right)*120[/mm]
> >
>
>
> Mir ist der 3. Schritt, also wie ich auf die "entstehung"
> der 34 komme absolut unklar...
Na, du hast 34 = 1*77+(-1)*43
Jetzt kannst du aus der ersten Gleichung 43 = 1*120+(-1)*77 einsetzen.
Es ergibt sich
34 = 1*77+(-1)*(1*120+(-1)*77) = ...
Grüsse, Amaro
|
|
|
| |
|
okay...soweit bin ich natürlich dabei...aber das ist doch noch lange nicht alles...
Wie mache ich jetzt weiter?
mit der 9 und der 7 damit ich die dann ebenfalls in eine Gleichung geben kann, oder nehme ich die Gleichung nach der 34 setzte den Äqivalenzpfeil und löse die 9 auf?
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 19:32 Sa 29.05.2010 | | Autor: | leduart |
Hallo
jetzt nimmst du die 9 dran, bis du bei der 1 bist.
Gruss leduart
|
|
|
| |
|
Die Frage ist ja, wie ich die 9 jetzt umrechne....
Die Gleichung der 34 konnte ich ja aufstellen, weil ich vorher die 120 und die 77 zurückgerechnet habe und daraus dann eine Gleichung gemacht habe...
Wie komme ich jetzt an die 9?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:23 Sa 29.05.2010 | | Autor: | kunterbunt |
Wenn sich jemand in der Lage sieht, mir zu antworten, wäre das genial, weil ich das gerne heute noch schaffen würde...
|
|
|
| |
|
Hallo kunterbunt,
> Die Frage ist ja, wie ich die 9 jetzt umrechne....
> Die Gleichung der 34 konnte ich ja aufstellen, weil ich
> vorher die 120 und die 77 zurückgerechnet habe und daraus
> dann eine Gleichung gemacht habe...
> Wie komme ich jetzt an die 9?
>
>
Wird der euklidische Algorithmus weitergeführt, so ergibt sich zunächst
[mm]43=1*34+9 \gdw \red{9}=1*\blue{43}+\left(-1\right)*\green{34}=1*\blue{\left(1*120+\left(-1\right)*77\right)}+\left(-1\right)*\green{\left(2*77+\left(-1\right)*120\right)}=\red{\alpha*77+\beta*120}[/mm]
Weiter ergibt sich
[mm]34=3*9+7 \gdw 7=1*\green{34}+\left(-3\right)*\red{9}=1*\green{\left(2*77+\left(-1\right)*120\right)}+\left(-3\right)*\red{\left(\alpha*77+\beta*120\right)}=\gamma*77+\delta*120[/mm]
Gruss
MathePower
|
|
|
| |
|
so...ich glaube, dass ich kurz vor dem Ziel stehe...
Ich hab jetzt 120,77,43,34,9 und 7 mit den Äquivalenzzeichen aufgelöst...
>
> [mm]43=1*34+9 \gdw \red{9}=1*\blue{43}+\left(-1\right)*\green{34}=1*\blue{\left(1*120+\left(-1\right)*77\right)}+\left(-1\right)*\green{\left(2*77+\left(-1\right)*120\right)}=\red{\alpha*77+\beta*120}[/mm]
>
> Weiter ergibt sich
>
> [mm]34=3*9+7 \gdw 7=1*\green{34}+\left(-3\right)*\red{9}=1*\green{\left(2*77+\left(-1\right)*120\right)}+\left(-3\right)*\red{\left(\alpha*77+\beta*120\right)}=\gamma*77+\delta*120[/mm]
Jetzt muss ich nur noch wissen, wie ich auf alpha, beta, gamma und delta komme...dann hab ich es endlich
Liebste Grüße und vielen Dank für die bisherige Hilfe!
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 14:56 So 30.05.2010 | | Autor: | leduart |
Hallo
ais blau + grün in er ersten Zeile,ergibt sich [mm] \alpha [/mm] und [mm] \beta.
[/mm]
warum rechnest du mit den Tips gar nicht rum?
in der nähsten Zeile auch einfach ausrechnen!
Gruss leduart
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:42 So 30.05.2010 | | Autor: | kunterbunt |
Ich habs-ich habs-und ich habs verstanden!
Dankesehr!
|
|
|
|
