Erweiterter Euklidischer Algorithmus: Verstaendnisfrage
-
Hi!
Ich hab ein Verstaendnisproblem mit folgendem Ausschnitt aus unserer Mathe-Vorlesung:
Gibt es ganze Zahlen u, v mit 450 = 274u + 113v?
Falls ja, dann ist ggT(274, 113) := g ein Teiler von 450 (g * t)
g*t = 274u't + 113v't (mit u't = u, v't = v)
Ich versteh zwar die weitere Rechnung, die daraufhin folgt, aber: warum muss g zwingend ein Teiler von 450 sein?
-
Es ist 450 = 274u + 113v = g[(274/g)u + (113/g)v] mit ggT(274/g,113/g) = 1.
-
sorry, aber ich versteh kein Wort
-
a = qb <==> b|a
-
ok, das ist klar, aber in dem Fall ists ja eher etwas in der Form
c = xa + yb
und ich versteh nicht, warum c vom ggT(a, b) geteilt werden _MUSS_
Bitte erklaers mir etwas ausfuehrlicher
-
450 = 274u + 113v = g\underbrace{[(274/g)u + (113/g)v]}{\in \mathbb{Z}
-
hmm... ok, das hast du vorhin schon hingeschrieben, aber ich raffs immer noch nicht (sorry wenn ich nerve)....
Ich bin meine Mitschriften nochmal durchgegangen, und dabei auf folgenden Satz gestossen:
Es gibt u, v ε Z, a, b, ε Z mit
c = u*a + v*b
genau dann, wenn ggT(a, b) die Zahl c teilt
Im Skriptum wird der Satz leider nie erwaehnt, geschweige denn genauer erklaert oder gar bewiesen. Es waer mir eine grosse Hilfe (da der Satz in spaeteren Kapiteln noch oefters verwendet wird), wenn du's nochmal versuchen koenntest, mir das genauer zu erklaeren (oder auch nur einen - halbwegs verstaendlichen - Beweis liefern koenntest (hab selber leider keinen im Netz gefunden)).
-
Hi,
das sieht man so:
g:=ggt(a,b), c = u*a + v*b = u*gx + v*gy = g(ux + vy) => g | cRückrichtung ähnlich.
Jockel
-
g := ggT(a,b); c = gq; a' := a/g, b' := b/g ==> ggT(a',b') = 1 ==> es existieren u,v \in Z mit ua' + vb' = 1 (erweiterter euklid. Alg.) ==> ua + vb = g ==> c = gq = (uq)a + (vq)b
-
hmm... ich hab zwar ehrlich gesagt immer noch nicht verstanden, warum es kein c geben kann, das NICHT vom ggt(a, b) geteilt wird und trotzdem die Bedingung erfuellt. Aber ich hab genug verstanden, um die Rechenaufgaben und den weiteren Text im Skriptum zu verstehen
Vielen dank!
-
Blue-Tiger schrieb:
hmm... ich hab zwar ehrlich gesagt immer noch nicht verstanden, warum es kein c geben kann, das NICHT vom ggt(a, b) geteilt wird und trotzdem die Bedingung erfuellt.
Weil aus der Erfüllung der Bedingung folgt, dass ggT(a,b)|c.