Lemma von Bézout < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:25 Fr 08.02.2019 | | Autor: | magics |
Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
| Aufgabe | Lemma von Bézout:
Jede Folge $a_1, ..., a_n$ aus ganzen Zahlen kann man mit einer Zahlenfolge $r_1, ..., r_n$ linearkombinieren, sodass $d = a_1*r_1 + ... + a_n * r_n$ und $d = ggT(a_1, ..., a_n)$
Dies soll nun für den Fall $n=2$ bewiesen werden. |
Hallo,
ich komme beim wohl letzten Schritt nicht weiter. Bisher hab ich folgendes gemacht:
Sei $e = ggT(a,b)$
Sei $M:=\{x: x = s*a + t*b: s,t \in \IZ \}$
Sei $d = min(M)$ (Wir binden die Minimalbedingung an d)
Nach dem Lemma gilt: $d = a*s + a*t, s,t \in \IZ$
Nun folgt eine Deduktion über die Teilbarkeit von d:
$e|ggT(a,b) \Rightarrow e|a, e|b$
$e|a \wedge e|b \Rightarrow e|as \wedge e|bt \Rightarrow e|as+bt \Rightarrow e|d$
Sei $q:= divisor(a,d)$ mit $a = q*d + r, 0 \le r < d$
Wir ersetzen nun d durch $ a*s + a*t$ und lösen nach r auf:
$a = q(a*s+b*t)+r$
${r = a - q(a*s + b*t) = \red{a(1+q*s)+b(-q*t)}$
Aus der roten Darstellung soll man nun wegen des Minimalprinzips schließen können, dass $r = 0$ sein muss. Ich sehe allerdings nicht wie.
Grüße
Thomas
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:04 Fr 08.02.2019 | | Autor: | leduart |
Hallo
ich verstehe nicht ganz, warum du das nicht einfach mit dem Euklidischen Algorithmus machst?
Gruß lul
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:33 Fr 08.02.2019 | | Autor: | magics |
Hallo leduart,
der Euklidische Algorithmus (rückwärts) lässt sich meines Wissens nur an ganz konkreten Zahlenbeispielen nachvollziehen und eignet sich nicht explizit als formalen Beweis. Ich mag mich da jedoch täuschen.
Ich glaube die Antwort auf meine Frage ist:
$r = [mm] a(1+q\cdot{}s)+b(-q\cdot{}t)$
[/mm]
Wegen $e|a$ und $e|b$ gilt auch [mm] $e|a(1+q\cdot{}s)+b(-q\cdot{}t)$
[/mm]
Somit kann r nur ein Vielfaches von a und b sein und damit wäre es 0.
Ich finde es an sich schon richtig, sich einen Beweisweg zu suchen, den man versteht und so. Ich kann mich nur schwer damit abfinden bestimmte Wege nicht nachvollziehen zu können und bin da manchmal etwas überakribisch.
Danke dir trotzdem für deinen Hinweis!
Lg
Thomas
|
|
|
|
