ggT als Linearkombination ... beweis?
-
Hallo!
wenn für 2 zahlen a,b gilt: d=ggT(a,b) , so kann man den ggT ja auch als Linearkombination aus a und b darstellen. Also: d=ax+by
wenn ich mir das so überlege erscheint es mir logisch, aber ich kann mir da selbst keinen beweis zusammen reimen
kann mir das jemand anschaulich erklären? wenn's geht bitte nicht zu kompliziert.danke im voraus!
-
Z ist Hauptidealring, (a,b) = (d) ist das kleinste Ideal, das (a) und (b) enthält <==> teilt, also d = ggt.
-
hm, damit kann ich leidr nicht viel anfangen
gibt es dafür keine einfachere erklärung?
-
konstruktiv durch Erweiterten euklidischen Algo
-
hm naja wenn ich mir http://de.wikipedia.org/wiki/Erweiterter_Euklidischer_Algorithmus
anschau, seh ich da keinen wirklcihen mathematischen beweis.
es wird zwar erklärt wie der algo funktioniert aber mehr nicht
-
Ja, das reicht doch. Die Angabe eines Verfahrens ist der Beweis der Existenz eines solchen Verfahrens.
-
naja aber ich bräuchte so einen beweis etwas kürzer und eher in mathematischer form (sprich formeln) für ne facharbeit
-
-
Der_ggT schrieb:
naja aber ich bräuchte so einen beweis etwas kürzer und eher in mathematischer form (sprich formeln) für ne facharbeit
Warum? Du gibst ein allgemein gültiges Verfahren an, mit dem du die Linearkombination errechnen kannst. Da hast du deinen Beweis. Wofür dann noch Formeln? So ist der Beweis doch noch viel praktischer, weil du nicht nur die Existenz der Linearkombination gezeigt hast, als Bonus bekommst du noch gleich ein Verfahren geschenkt. Damit machst du jeden Mathematiker glücklich!
-
Wenn Du den Euklidischen Algorithmus rückwärts anwendest, kommst Du ja wie bereits mehrfach gesagt zu deiner Lösung.
Bsp:
d = gcd(10,6) = 21.) Euklidischer Alg.
10 = 6 * 1 + 4
6 = 4 * 1 + 2
4 = 2 * 2=> d = 2
2.) Rückwärts angewandt (in vorletzter Zeile beginnen)
2 = 6 - 4 * 1 = 6 - (10 - 6 * 1) * 1 = 6 - 10 + 6 = 2 * 6 - 1 * 10
voila: a = 2, b = -1
Schreibst Du das Ganze nun noch sauber allgemein auf, hast Du Deinen Beweis. Konstruktiv und sehr praktisch. Anders wirst Du den wahrscheinlich auch in keinem Buch finden.