Euklidischer Algorithmus

11.01.2007, 20:09

Blador

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&#8901 traurig

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!

11.01.2007, 20:13

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)

11.01.2007, 21:35

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:

$\begin{eqnarray*} 4 =4 \cdot 1 + 0 \end{eqnarray*}$ anstelle von $\begin{eqnarray*} 16 =16 \cdot 1 \end{eqnarray*}$

wie es dann weitergeht? nun du bist quasi fertig: Löse die klammer doch mal auf smile

12.01.2007, 06:20

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!

12.01.2007, 09:18

Ambrosius

Auf diesen Beitrag antworten »

einfach durch ganz banales auflösern einer klammer

$\begin{eqnarray*} 1 = 17 - 4 \cdot (55 - 3 \cdot 17) = 17 - 4 \cdot 55 + 12 \cdot 17 \end{eqnarray*}$

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

12.01.2007, 10:22

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.