größter gemeinsamer Teiler als Lin-kombination

06.05.2009, 18:55

größter gemeinsamer Teiler als Lin-kombination

Ich stehe irgendwie gerade ein wenig auf dem Schlauch, was folgenden Beweis angeht (euklidischer Algorithmus ist bekannt):

Seien $\begin{eqnarray*} a,b \in \mathbb{Z} \end{eqnarray*}$ mit $\begin{eqnarray*} (a,b)\neq (0,0) \end{eqnarray*}$ . Zu zeigen:

$\begin{eqnarray*} \mathrm{ggT}(a,b)=\mathrm{min}\{\alpha a + \beta b | \alpha, \beta \in \mathbb{Z} \mathrm{~und~} \alpha a + \beta b > 0 \} \end{eqnarray*}$

So, ich bin über einen Widerspruchsbeweis rangegangen.
Dass $\begin{eqnarray*} \mathrm{ggT}(a,b)<\mathrm{min}(...) \end{eqnarray*}$ zum Widerspruch führt ist sofort klar.
Nur mit der Umkehrung tue ich mich irgendwie schwer:
$\begin{eqnarray*} \mathrm{ggT}(a,b)>\mathrm{min}(...) \end{eqnarray*}$
Daraus folgt natürlich sofort die Existenz einer Kombination $\begin{eqnarray*} \alpha a + \beta b=c<\mathrm{ggT}(a,b) \end{eqnarray*}$ . Aber wieso kann das nicht gehen?

Gruß
MI

06.05.2009, 19:10

Ungewiss

Auf diesen Beitrag antworten »

$\begin{eqnarray*} 0<\alpha a + \beta b<\mathrm{ggT}(a,b) \end{eqnarray*}$

Ich würde sagen, dass ein Widerspruch entsteht, wenn man duch ggt(a, b) teilt, denn einerseits ist der Ausdruck in der Mitte dann eine natürliche Zahl, andererseits liegt er zwischen 0 und 1.

06.05.2009, 19:12

jester.

Auf diesen Beitrag antworten »

Ah, du hörst also auch die LA I bei Prof. Nebe. Big Laugh

Tja, warum geht das nicht? Gute Frage. Ich bin an den Beweis insgesamt etwas anders rangegangen, also müsste ich jetzt auch erst mal ein bisschen überlegen.

Aber ich wollte natürlich mitteilen, dass wir die gleiche Vorlesung hören. Big Laugh

Edit: Die Idee von Ungewiss finde ich gut.

06.05.2009, 19:16

Auf diesen Beitrag antworten »

@jester.
Das wusste ich bereits vorher. Augenzwinkern

@Ungwiss:
Danke!
Der Gedanke, dass aus dem Teiler eine natürliche Zahl entsteht, war mir auch schon gekommen - aber dass das dann natürlich kleiner 1 sein muss...
Oh Mann, manchmal sieht man den Wald vor lauter Bäumen nicht...

Gruß
MI

07.05.2009, 10:56

Felix

Auf diesen Beitrag antworten »

Zitat:

Dass $\begin{eqnarray*} \mathrm{ggT}(a,b)<\mathrm{min}(...) \end{eqnarray*}$ zum Widerspruch führt ist sofort klar

Warum ist das Klar?
Kann das Minimum nicht auch größer 1 sein ?

07.05.2009, 23:29

Auf diesen Beitrag antworten »

Wegen folgender Überlegung:

Der euklidische Algorithmus liefert den ggT (wir nehmen den positiven, somit ist ggT>0 gegeben) in der Form:
$\begin{eqnarray*} \alpha a + \beta b = \mathrm{ggT}(a,b) \end{eqnarray*}$

Damit ist aber $\begin{eqnarray*} \mathrm{ggT}(a,b)\in \{\alpha a + \beta b| \alpha, \beta \in \mathbb{Z} \mathrm{~und~} \alpha a + \beta b >0 \}=: M \end{eqnarray*}$
und damit kann
$\begin{eqnarray*} \mathrm{ggT}(a,b)<\mathrm{min}(M) \end{eqnarray*}$
natürlich nicht gelten.

Gruß
MI

EDIT: Wir haben heute in der Globalübung noch bewiesen, dass sogar gilt:
$\begin{eqnarray*} g\mathbb{Z}=a\mathbb{Z}+b\mathbb{Z} \end{eqnarray*}$ mit $\begin{eqnarray*} g=\mathrm{ggT}(a,b) \end{eqnarray*}$ .
Hätten wir das vorher gewusst, wäre die Aufgabe natürlich witzlos gewesen Big Laugh

08.05.2009, 06:34

Felix

Auf diesen Beitrag antworten »

Zitat:

Der euklidische Algorithmus liefert den ggT (wir nehmen den positiven, somit ist ggT>0 gegeben) in der Form: $\begin{eqnarray*} \alpha a + \beta b = \mathrm{ggT}(a,b) \end{eqnarray*}$

Man kann den Beweis übrigens auch über Ideale führen und somit allgemein in jedem Hauptidealring beweisen ...

08.05.2009, 17:29

Auf diesen Beitrag antworten »

Wie würde das denn aussehen?
Rein interessehalber. Wir sind leider noch nicht so weit. Ich kenne bisher gerade einmal die Definition eines Ideals.

Gruß
MI

08.05.2009, 20:11

system-agent

Auf diesen Beitrag antworten »

Edit:
Hier stand unsinn, bitte Beitrag löschen !

09.05.2009, 10:33

Elvis

Auf diesen Beitrag antworten »

@Felix
das ist grober Unfug. Euklidische Ringe sind Hauptidealringe. Wenn die Umkehrung gelten sollte, müsste man in jedem Hauptidealring eine Gradabbildung definieren können, die dem Euklidischen Algorithmus zugrundeliegt.

Es gilt: R euklidisch ---> R Hauptidealring ---> R noethersch ---> R faktoriell.

In euklidischen Ringen kann man den ggT durch den Euklidischen Algorithmus berechnen.
In Hauptidealringen lassen sich ggt und kgV idaltheoretisch charakterisieren.
In faktoriellen Ringen sind ggT und kgV bestimmte Produkte aus Primfaktoren.

09.05.2009, 11:38

Felix

Auf diesen Beitrag antworten »

Zitat:

Original von Elvis
@Felix
das ist grober Unfug. Euklidische Ringe sind Hauptidealringe. Wenn die Umkehrung gelten sollte, müsste man in jedem Hauptidealring eine Gradabbildung definieren können, die dem Euklidischen Algorithmus zugrundeliegt.

Es gilt: R euklidisch ---> R Hauptidealring ---> R noethersch ---> R faktoriell.

In euklidischen Ringen kann man den ggT durch den Euklidischen Algorithmus berechnen.
In Hauptidealringen lassen sich ggt und kgV idaltheoretisch charakterisieren.
In faktoriellen Ringen sind ggT und kgV bestimmte Produkte aus Primfaktoren.

Ich habe mich auf das hier berufen: http://de.wikiversity.org/wiki/Hauptidealbereich/Bezout_Euklid_Faktoriell/Abschnitt

Ist in diesem Beweis etwas falsch?

lg

09.05.2009, 13:54

Elvis

Auf diesen Beitrag antworten »

Nein, nicht falsch. Auch in Hauptidealringen kann man den $\begin{eqnarray*} ggT(x_1,...,x_n) \end{eqnarray*}$ als Linearkombination von $\begin{eqnarray*} x_1,...,x_n \end{eqnarray*}$ darstellen. Das ist ein Existenzbeweis.
Darüberhinaus hat man in euklidischen Ringen ein Konstruktionsverfahren - den Euklidischen Algorithmus - um den ggT zu finden und als Linearkombination darzustellen. Das funktioniert in "billigeren" Ringen nicht.
Ich hatte dich so verstanden, daß du glaubtest, diese Linearkombination auch mit Euklidischem Algorithmus in Hauptidealringen berechnen zu können - das geht nicht.

09.05.2009, 15:36

Felix

Auf diesen Beitrag antworten »

Du hast recht, dieser Beweis geht nicht ganz auf die Aufgabe ein - deswegen hast du mich auch falsch verstanden ...

Neue Frage »

Antworten »

größter gemeinsamer Teiler als Lin-kombination

Verwandte Themen