[Diskrete] Euklidischer Alg. mit Rückwärtseinsetzen

[CrazyPumuckl]

Hi,

habe mich grade mal am euklidischen Alg. mit Rückwärtseinsetzen versucht. Irgendwie klappte das nur bei dem Beispiel des KGÜ-Leiters.
Habe folgende Aufgaben: (ggT (a,b) = s*a+t*b; s soll bestimmt werden)

1.) a = 2006, b = 802
2.) a = 8, b = -13
3.) a = 777, b = 581

Könnte mir jemand mal zeigen (an einem der Beispielaufgaben am besten) wie man das nun löst (mit o.g. Verfahren, und ohne dieses u' =... t' =...)

Lösungen sind: s = 2 (für 1.), s = 5 (für 2.), s = 3 (für 3.).

Danke.

[maddinac]

wie funktioniert denn der algorithmus mit rückwärtseinsetzen?
Ich kenn nur den der im Buch von der Steger beschrieben ist.
Der funktioniert so, dass man erstmal soweitrechnet bis man den ggt gefunden hat und von da dann von 1 und 0 ausgehend werte zurückliefert.

[CrazyPumuckl]

Könntest du da mal ein Beispiel zu rechnen? Das mit dem ggt finden ist mir klar, nur was dann danach kommt nicht so ganz...

[Teq]

Also hier mal das ganze für a = 2006, b = 802

Zuerst wie immer ggT
2006 = 2*802 + 402
802 = 1*402 + 400
402 = 1*400 + 2
400 = 20 * 2

Soweit so gut, das ist klar

Jetzt Rückwärts:

2 = 402 - 400
= 402 - 1*(802 - 402)
= 2*402 - 1*(802)
[An der Stelle hab ich bisher immer etwas gehangen, weil ich versucht hab 802 anders auszudrücken *lol*]
= -1 * 802 + 2 * 402
= -1 * 802 + 2 * (2006 - 2*802)
= -5 * 802 + 2 * 2006
= 2 * 2006 - 5*802
Fertig, s = 2, t = -5.

[CrazyPumuckl]

Hey,

Vielen dank, genau so hab ich das gesucht
Ich habe glaube ich an der gelichen Stelle gehangen wie Du, weil ich versucht hab jede Gleichung umzuformen und in die letzte einzusetzen.

Thx a lot!

[kb]

ich versuch da mal Farbe reinzubringen, damit man crazy, was wo eingesetzt wurde:

2006 = 2*802 + 402
802 = 1*402 + 400
402 = 1*400 + 2
400 = 20 * 2


2 = 402 - 1*400
(400 durch die 2 "drüberliegenden ausdrücken)
= 402 - 1*(802 - 1*402)
= 2*402 - 1*(802)
= -1 * 802 + 2 * 402
(402 durch die 2 "drüberliegenden ausdrücken)
= -1 * 802 + 2 * (2006 - 2*802)
= -5 * 802 + 2 * 2006
= 2 * 2006 - 5*802
Fertig, s = 2, t = -5.

--edit--
douh, zu spät ^^

ich kenn das auch so:

Code: Alles auswählen

(von unten nach oben betrachten)
q    s    t

2 |  2 | -5
1 | -1 |  2
1 |  1 | -1
2 |  0 |  1

man fängt unten an mit s=0 und t=1, und füllt  die Tabelle nach folgender Formel:
s = t_alt
t = s_alt - q*t_alt


Meint ihr man kann das so beim Triesch verwenden?

[Nomar]

Im Script für Lineare Algebra 1 vom Plesken steht der Algorithmus auch drin, mit etwas anderer Rückwärtseinsetzmethode (mit Matritzen).
Wer das Script hat: In der WS04/05er Version ist es Algorithmus 4.13, auf Seite 45f.

[CrazyPumuckl]

Also der Thorsten hat das ja auch mal mit den s_alt und so gemacht. allerdings fand ich das kompiziert. wenn ich mir deine tabelle anschaue finde ich das jetzt voll übersichtlich! willst du nicht mal den thorsten ersetzen?

Thx für den Tipp!

[CrazyPumuckl]

Hm, und wie sähe das jetzt für die 2.) aus mit 8 und -13? darf q negativ sein? ich hab dann aber irgendwie immer ein anderes s raus, aber nicht 5

[Tommytb]

402 = 1*400 + 2
400 = 20 * 2

Soweit so gut, das ist klar

Hmm, da habe ich so meine Zweifel... aber tut ja nicht sonderlich viel zur Sache, bei diesem Beispiel...

[kb]

hehe, jo, da fehlt ne 0 ^^

@crazy
also 8 und -13

8 = -1*(-13) -5
-13 = 3*(-5) +2
-5 = -3*2 + 1
2 = 2*1

Code: Alles auswählen

 q    s    t

-1 | -8 | -5
 3 |  3 | -8
-3 |  1 |  3
 2 |  0 |  1


ggT(8,-13) = 1 = -8*8 + (-5)*(-13)

die Darstellung ist soweit ich weiß nicht eindeutig. s=5 und t=3 wär aber auch ne Lösung

[CrazyPumuckl]

Genau, bei mir wars auch nicht immer eindeutig. Hoffe mal dass es in der Klausur nicht so sein wird, dass s innerhalb eines bestimmten Wertebereichs liegen muss (auf dem MC-Blatt war das 1 <= s <=5).

Thx.

[kb]

Da |-13| > |8| sollte man hier vielleicht a und b "vertauschen".
Dann musst du in der von mir angegebenen Tabelle aber auch mit t=-1 anfangen.

-13 = -2*8 +3
8 = 3*3 -1
3 = -3*(-1)

Code: Alles auswählen

 q   s   t

-2 |  3 |  5
 3 | -1 |  3
-3 |  0 | -1

da du ja jetzt a und b "vertauscht" hast, musst du das auch mit s und t machen. Und so kommst du auch auf die s=5

Wenn du nicht mit t=-1 anfängst erhälst du als s=-5 und t=-3. Durch einsetzen erhälst du dann ggT=-1 , also musst du alles mit -1 multiplizieren und du hättest wieder s=5 und t=3

[Teq]

402 = 1*400 + 2
400 = 20 * 2

Soweit so gut, das ist klar

Hmm, da habe ich so meine Zweifel... aber tut ja nicht sonderlich viel zur Sache, bei diesem Beispiel...

Warum??
Wenn was falsch ist, sag besser jetzt was genau, ich muss Diskrete nämlich auch noch schreiben *g*

[kb]

@Teq

402 = 1*400 + 2
400 = 20 * 2

Soweit so gut, das ist klar

Hmm, da habe ich so meine Zweifel... aber tut ja nicht sonderlich viel zur Sache, bei diesem Beispiel...

hehe, jo, da fehlt ne 0 ^^

400 = 200 * 2 ;]