Euklidischer Algorithmus

Neue Frage »

Blador Auf diesen Beitrag antworten »
Euklidischer Algorithmus
Nabend,

Ich beschäftige mich zurzeit mit dem euklidischen Algorithmus.
Nehmen wir als Beispiel a=17 und b=55. Zuerst berechnet man ja den ggT, das wäre 1 da:
55=3⋅17+4
17=4⋅4+1
16=16⋅1

Nach der Vielsummendarstellung gilt ja: d=xa+yb
Wie kommt man nun auf das x und y? Man muss ja die Gleichungskette von unten nach oben auflösen, bin soweit gekommen:
1=17−4⋅4
1=17−4&#8901traurig 55−3⋅17)
Hier komm ich nun nicht mehr weiter...wie bekommt man denn jetzt das x und y? unglücklich

Dankeschön, für eure Antworten!
Blador Auf diesen Beitrag antworten »

Sry jetzt sieht man die ganzen klammern da nicht.. :-/

Hier nochmal:
55=3*17+4
17=4*4+1
16=16*1

Wo ich dann nicht weiterkomme:
1=17-4*4
1=17-4*(55-3*17)
 
 
Ambrosius Auf diesen Beitrag antworten »

seh ich das richtig, das du den ggt also als Linearkombination von a und b darstellen willst?

zunächst mal ein schreibfehler im Letzten schritt des Algortihmus:
da muss es so heißen:

anstelle von

wie es dann weitergeht? nun du bist quasi fertig: Löse die klammer doch mal auf smile
Blador Auf diesen Beitrag antworten »

Hi,

Oh ja, danke. Keine Ahnung wie ich auf 16 gekommen bin..smile

Also, ich will das ja in form von d=xa+yb
die letzte Zeile ist ja
1=17-4*(55-3*17) a und b weiß ich ja schon und d ist gleich 1. Jetzt fehlt mir x und y, wie soll ich denn die klammer auflösen, damit ich auf die beiden Werte komme?
Danke!
Ambrosius Auf diesen Beitrag antworten »

einfach durch ganz banales auflösern einer klammer



Jetzt packst du noch die 17 und 12*17 zusammen und hast deine Darstellung.
AD Auf diesen Beitrag antworten »

Wenn es nicht nur um die Bestimmung des ggT, sondern auch die Ermittlung dieser genannten Faktoren, läuft das ganze auch unter dem Begriff

Erweiterter Euklidischer Algorithmus ,

im Unterschied zum "gewöhnlichen" Euklidischen Algorithmus. Der Algorithmus ist eigentlich derselbe, nur werden diese Faktoren mitprotokolliert. Das nur als Hinweis.
Blador Auf diesen Beitrag antworten »

Zitat:

Jetzt packst du noch die 17 und 12*7 zusammen und hast deine Darstellung.


Wie meinst du das zusammenpacken? verwirrt
Ambrosius Auf diesen Beitrag antworten »

addieren. meinte natürlich 12*17. habs oben schon verbessert.

also hast du 1*17 + 12*17 =????
Blador Auf diesen Beitrag antworten »

Okay, habs jetzt. Danke! smile
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »