Lineare Darstellung ggT

04.05.2008, 19:46

Ratlos12

Lineare Darstellung ggT

Ich stehe gerade vor einem kleinen Problem. Ich möchte folgendes beweisen:

Für ganze Zahlen m, n gilt: ggT(a, b) = ma + nb

Ich hatte gelesen, dass man das durch "aufsteigende" Induktion beweisen kann. Das hab ich aber noch nie gehört :-(
Trotzdem hab ich versucht die Aussage zu beweisen. Vielleicht kann mir ja jemand seine Menung dazu sagen.

Seien a, b ganze Zahlen, (a, b) sei gegeben mit $\begin{eqnarray*} 2 \leq b \leq a \end{eqnarray*}$ . Sei I = { ma + nb : m,n aus ganzen Zahlen} Ideal .

a, b $\begin{eqnarray*} \in \end{eqnarray*}$ I. Behauptung: $\begin{eqnarray*} a_i, b_i \in I \end{eqnarray*}$ für $\begin{eqnarray*} 1 \leq i \leq n \end{eqnarray*}$ .

I.A.: i=1
$\begin{eqnarray*} a_1 = 1 \cdot a + 0 \cdot b \end{eqnarray*}$
$\begin{eqnarray*} a_1 = 0 \cdot a + 1 \cdot b \end{eqnarray*}$

I.V.: Es gelte $\begin{eqnarray*} a_i, b_i \in I \end{eqnarray*}$ für $\begin{eqnarray*} 1 \leq i \leq n \end{eqnarray*}$ .

I.S.: ggT ist durch Formel $\begin{eqnarray*} a_i = q \cdot b_i + r \end{eqnarray*}$ darstellbar.
Es gilt also
$\begin{eqnarray*} a_1 = q \cdot b_1 + r \end{eqnarray*}$
$\begin{eqnarray*} a_2 = q \cdot b_2 + r \end{eqnarray*}$
$\begin{eqnarray*} a_3 = q \cdot b_3 + r \end{eqnarray*}$
...
$\begin{eqnarray*} a_i = q \cdot b_i + r \end{eqnarray*}$
$\begin{eqnarray*} a_{i+1} = q \cdot b_{i+1} + r \end{eqnarray*}$

Der ggT von allen Paaren $\begin{eqnarray*} (a_i, b_i) \end{eqnarray*}$ ist immer gleich, d.h. es gilt

ggT $\begin{eqnarray*} (a_1, b_1) \end{eqnarray*}$ = ggT $\begin{eqnarray*} (a_2, b_2) \end{eqnarray*}$ = ...= ggT $\begin{eqnarray*} (a_i, b_i) \end{eqnarray*}$ = ggT $\begin{eqnarray*} (b_i, r) \end{eqnarray*}$ = $\begin{eqnarray*} (a_{i+1}, b_{i+1}) \end{eqnarray*}$

Muss ich jetzt noch sagen, dass $\begin{eqnarray*} b_{i+1} = r = a_i - q \cdot b_i \in I \end{eqnarray*}$

Also sind $\begin{eqnarray*} a_{i+1} und b_{i+1} \in I \end{eqnarray*}$

Ich bin echt über jede Hilfe dankbar. :-)

04.05.2008, 19:48

Auf diesen Beitrag antworten »

Zitat:

Original von Ratlos12
Für ganze Zahlen m, n gilt: ggT(a, b) = ma + nb

Nein, so gilt es ganz gewiss nicht. Sondern:

Zitat:

Es gibt (!) ganze Zahlen m, n mit: ggT(a, b) = ma + nb

Ein gewaltiger Unterschied!

04.05.2008, 19:53

Ratlos12

Auf diesen Beitrag antworten »

Oh danke, ich hatte das aus einem englischen Buch und anscheinend falsch übersetzt. Wie beweise ich die Aussage?

04.05.2008, 20:43

Ratlos12

Auf diesen Beitrag antworten »

Ich würd das Ganze ja gern verstehen. Wie gesagt, hab ich das aus einem englischen Buch übersetzt. Dort wird das durch die aufsteigende Form der Induktion ansatzweise bewiesen. Und zwar wie folgt:

Als Start haben wir
$\begin{eqnarray*} a_1 = 1 \cdot a + 0 \cdot b \end{eqnarray*}$
$\begin{eqnarray*} a_1 = 0 \cdot a + 1 \cdot b \end{eqnarray*}$ ,
daher ist die Aussage wahr für i = 1.
Wenn $\begin{eqnarray*} a_i \end{eqnarray*}$ und $\begin{eqnarray*} b_i \end{eqnarray*}$ beide von der Form ma + nb sind, ist das Gleiche für ihre Differenz wahr, folglich für $\begin{eqnarray*} a_{i+1} \end{eqnarray*}$ und $\begin{eqnarray*} b_{i+1} \end{eqnarray*}$ . Daher sind alle Zahlen, die durch das Paar (a,b) mit dem eukl. Algorithmus entstehen von der Form ma + nb.

Das war der Beweis aus dem Buch, mit dem ich nicht so wirklich was anfangen kann. Ich steige schon ab dem Punkt "Aussage wahr für i = 1" aus. Die nächsten Folgerungen versteh ich nicht. Kann mir das vielleicht jemand etwas ausführlicher erklären? verwirrt

04.05.2008, 21:32

system-agent

Auf diesen Beitrag antworten »

Du solltest auch dazu sagen wie der ggT definiert war, denn manchmal definiert man den ggT genau mit der Aussage die du zeigen willst.

Edit:
Such mal nach "Lemma von Bézout", zb http://en.wikipedia.org/wiki/Bézout's_identity

Neue Frage »

Antworten »

Lineare Darstellung ggT

Verwandte Themen