ggT(a,b) = ggT(a - b,b)

10.07.2017, 14:52

marin_zi

Auf diesen Beitrag antworten »

ggT(a,b) = ggT(a - b,b)

Hallo

Ich wird öfters erwähnt dass der ggT(543,234) den gleich ggT(543 - 234,234) hat.
Und dann wird mit dieser Regel allerhand angestellt und sachen vereinfacht.

Ich verstehe aber nicht warum das so sein soll wann und wo und mit welcher Überlegung man darauf gekommen ist.

Was ist das für eine Regel ?

Grüße
Martin

10.07.2017, 15:27

IfindU

Auf diesen Beitrag antworten »

RE: ggT(a,b) = ggT(a - b,b)
Das ist keine Eigenschaft vom groessten gemeinsamen Teiler. Das ist eine Eigenschaft aller Teiler.

Also $\begin{eqnarray*} \{ d \in \mathbb Z: d | a \text{ und } d | b \} = \{ d \in \mathbb Z: d | (a-b) \text{ und } d | b \} \end{eqnarray*}$ . Man kann leicht ueberpruefen, das das stimmt. Und wenn die Teilermenge identitisch,besitzen beide das gleiche goresste Element - den ggT.

10.07.2017, 15:50

marin_zi

Auf diesen Beitrag antworten »

RE: ggT(a,b) = ggT(a - b,b)
Hallo

Ok aber das befriedigt mich noch nicht. Also ich kann das jetzt versuchen Teilermengen von 2 Zahlen aufschreiben und schauen welche gemeinsamen Teiler es gibt. Dann hab ich eine Menge. Dann kann ich nochmal mal die Teilermenge von ggt(a-b,b) aufschreiben und sehe das dass auch wieder stimmt.

Aber was sagt mir das es kein Zahlenpaar gibt wo das dann doch mal nicht der Fall ist ?

Also ganz klick hats noch nicht gemacht ... verwirrt

verwirrt

10.07.2017, 15:54

IfindU

Auf diesen Beitrag antworten »

RE: ggT(a,b) = ggT(a - b,b)
Du sollst es auch nicht fuer konkrete Zahlen a,b ausrechnen, sondern zeigen, dass die Mengen fuer alle Zahlen a,b gleich sind.

10.07.2017, 23:40

marin_zi

Auf diesen Beitrag antworten »

RE: ggT(a,b) = ggT(a - b,b)
Hallo

Zitat:

Original von IfindU
Also $\begin{eqnarray*} \{ d \in \mathbb Z: d | a \text{ und } d | b \} = \{ d \in \mathbb Z: d | (a-b) \text{ und } d | b \} \end{eqnarray*}$ . Man kann leicht ueberpruefen, das das stimmt.

Ich kann das aber nicht und ich verstehe das auch nicht. Weder für einen ggt oder irgend einen Teiler. Wenn ich das könnte wüsste würde ich die Frage ja nicht stellen. Big Laugh

Big Laugh

Also es heißt ja wohl das d eine Zahl ist die a und b teilt und wenn das der Fall ist teilt d auch a-b.

Also ich nehme irgend eine Zahl d. Und ich nehme jetzt noch irgendeine Zahl zahl1.
Diese multipliziere ich mit d. Also: $\begin{eqnarray*} zahl1 \cdot d = a \end{eqnarray*}$ .

Jetzt hab ich zumindest eine Zahl a die durch d Teilbar ist. Das wiederhole ich mit zahl2. $\begin{eqnarray*} zahl2 \cdot d = b \end{eqnarray*}$ Jetzt hab ich 2 Zahlen die beide durch d Teilbar sind. $\begin{eqnarray*} (zahl1+zahl2)\cdot d \end{eqnarray*}$ bzw $\begin{eqnarray*} (zahl1-zahl2)\cdot d \end{eqnarray*}$ wäre jetzt auch durch d Teilbar. Aber zahl1 und zahl2 sind nicht a und b ? und warum sollte jetzt (a-b) auch durch d teilbar sein.

Also irgendwas fehlt mir noch um das zu verstehen ? Und ich sehe keine Zusammenhang und kann den nicht finden.

Daher die Frage: mit welcher Überlegung kommt man auf diese Aussage ?

11.07.2017, 05:30

IfindU

Auf diesen Beitrag antworten »

RE: ggT(a,b) = ggT(a - b,b)

Zitat:

Original von marin_zi
Ich kann das aber nicht und ich verstehe das auch nicht.

Unsinn! Was du danach schreibst ist genau die richtige Idee, wenn auch die Formulierung unsauber ist. Da $\begin{eqnarray*} d | a \end{eqnarray*}$ gibt es ein $\begin{eqnarray*} t_a \end{eqnarray*}$ mit $\begin{eqnarray*} t_a \cdot d = a \end{eqnarray*}$ , und analog ein $\begin{eqnarray*} t_b \end{eqnarray*}$ mit $\begin{eqnarray*} t_b \cdot d = b \end{eqnarray*}$ . Jetzt hattest du die richtige Idee $\begin{eqnarray*} (t_a - t_b) \cdot d \end{eqnarray*}$ zu betrachten. Multipliziere einmal aus und setze die vorigen Gleichungen ein. Damit folgt dann, dass $\begin{eqnarray*} d| (a-b) \end{eqnarray*}$ .

Wenn du jetzt noch zeigen kannst, dass wenn $\begin{eqnarray*} d|(a-b) \end{eqnarray*}$ und $\begin{eqnarray*} d|b \end{eqnarray*}$ gilt, schon $\begin{eqnarray*} d|a \end{eqnarray*}$ gilt so bist du bereits fertig!

Anzeige

11.07.2017, 09:55

marin_zi

Auf diesen Beitrag antworten »

RE: ggT(a,b) = ggT(a - b,b)

Zitat:

Original von IfindU
Multipliziere einmal aus und setze die vorigen Gleichungen ein.

Oh dann ist genau hier mein Problem.. Auf die Idee ausmultiplizieren kam ich auch schon. Aber das hat mir nichts gebracht.
Das ist doch keine Gleichung zumindest nicht was ich bis jetzt derzeit als Gleichung verstehe. Deswegen tue ich mir da wahrscheinlich so schwer.

Es gilt:

$\begin{eqnarray*} (t_a - t_b) \cdot d = ??? \end{eqnarray*}$
$\begin{eqnarray*} t_a \cdot d = a \end{eqnarray*}$
$\begin{eqnarray*} t_b \cdot d = b \end{eqnarray*}$

$\begin{eqnarray*} t_a \cdot d - t_b \cdot d= ??? \end{eqnarray*}$
$\begin{eqnarray*} a - b= ??? \end{eqnarray*}$

Woher weiß ich aus diesen Schritten das jetzt (a-b) durch d Teilbar sein sollte bzw das es so sein muss ? Ich weiß das die einzel Term a und b durch d teilbar sind aber was mit a-b ist weiß ich erstmal nicht.

11.07.2017, 12:08

IfindU

Auf diesen Beitrag antworten »

RE: ggT(a,b) = ggT(a - b,b)
Kennst du die Definition von Teilbarkeit? Eine Zahl $\begin{eqnarray*} c \end{eqnarray*}$ ist durch $\begin{eqnarray*} d \end{eqnarray*}$ teilbar, wenn eine (ganze) Zahl $\begin{eqnarray*} t \end{eqnarray*}$ existiert, so dass $\begin{eqnarray*} t \cdot d = c \end{eqnarray*}$ . D.h. man kann die Zahl $\begin{eqnarray*} c \end{eqnarray*}$ als Produkt von $\begin{eqnarray*} d \end{eqnarray*}$ und einer weiteren Zahl darstellen.

Das haben wir benutzt, um von $\begin{eqnarray*} d | a \end{eqnarray*}$ und $\begin{eqnarray*} d | b \end{eqnarray*}$ die beiden Gleichungen $\begin{eqnarray*} t_a \cdot d = a \end{eqnarray*}$ und $\begin{eqnarray*} t_b \cdot b = b \end{eqnarray*}$ herzuleiten.

Jetzt wollen wir explizit ein $\begin{eqnarray*} t \end{eqnarray*}$ (in Abhaengigkeit von $\begin{eqnarray*} t_a \end{eqnarray*}$ und $\begin{eqnarray*} t_b \end{eqnarray*}$ ) angeben. so dass $\begin{eqnarray*} t \cdot d = a -b \end{eqnarray*}$ . D.h.. es gilt $\begin{eqnarray*} d | (a-b) \end{eqnarray*}$ . Und das hast du schon effektiv getan. Du musst dir nur klar werden, dass du es getan hast.

11.07.2017, 13:27

marin_zi

Auf diesen Beitrag antworten »

RE: ggT(a,b) = ggT(a - b,b)
Hallo

Zitat:

Original von IfindU
Kennst du die Definition von Teilbarkeit? Eine Zahl $\begin{eqnarray*} c \end{eqnarray*}$ ist durch $\begin{eqnarray*} d \end{eqnarray*}$ teilbar, wenn eine (ganze) Zahl $\begin{eqnarray*} t \end{eqnarray*}$ existiert, so dass $\begin{eqnarray*} t \cdot d = c \end{eqnarray*}$ . D.h. man kann die Zahl $\begin{eqnarray*} c \end{eqnarray*}$ als Produkt von $\begin{eqnarray*} d \end{eqnarray*}$ und einer weiteren Zahl darstellen.

Ja ich denke die Definition von teilbarkeit habe ich verstanden. Zur Sicherheit beschreibe ich das nochmal in meinen Worten.

Wichtig ist das es um die ganzen Zahlen geht daher das "Z". ... , -3, -2, -1, 0, 1, 2, 3, ...

Also 6 ist durch 2 "teilbar". 7 ist nicht durch 2 "teilbar".
Also es darf beim teilen/ (und praktisch beim dividieren) kein Rest bleiben.

Daher kam ich auch auf die Idee wenn ich eine zahl suche die ich durch d teilen
soll, dann mache ich erstmal das umgekehrte umd multipliziere ganz einfach mit d. Dann habe ich sicher eine Zahl die durch d teilbar ist.

Zitat:

Original von IfindU
Jetzt wollen wir explizit ein $\begin{eqnarray*} t \end{eqnarray*}$ (in Abhaengigkeit von $\begin{eqnarray*} t_a \end{eqnarray*}$ und $\begin{eqnarray*} t_b \end{eqnarray*}$ ) angeben. so dass $\begin{eqnarray*} t \cdot d = a -b \end{eqnarray*}$ . D.h.. es gilt $\begin{eqnarray*} d | (a-b) \end{eqnarray*}$ . Und das hast du schon effektiv getan. Du musst dir nur klar werden, dass du es getan hast.

Hmm $\begin{eqnarray*} t \cdot d = a -b \end{eqnarray*}$ der Hinweis war jetzt gut .. moment mal ist das nicht einfach die formelle schreibweise für das ?

$\begin{eqnarray*} {a \over d} - {b \over d} = {t \over d} \end{eqnarray*}$

$\begin{eqnarray*} {a \over 4} - {b \over 4} = {t \over 4} \end{eqnarray*}$

$\begin{eqnarray*} {20 \over 4} - {12 \over 4} = {t \over 4} \end{eqnarray*}$

$\begin{eqnarray*} 5 \cdot { 1 \over 4} - 3 \cdot { 1 \over 4} = t \cdot {1 \over 4} \end{eqnarray*}$

Man bekommt mit der multiplikation immer ganze vielfache von d (wenn man dann kürzt). t muss dann aber eben auch durch den teiler kürzbar sein.
Ok vielleicht nicht so gut ausgedrückt verwirrt

verwirrt

11.07.2017, 13:40

IfindU

Auf diesen Beitrag antworten »

Das sind leider alles nur Zahlenbeispiele. Wenn ich dir sage, dass $\begin{eqnarray*} t:= t_a - t_b \end{eqnarray*}$ , kannst du nachrechnen, dass $\begin{eqnarray*} t \cdot d = a - b \end{eqnarray*}$ gilt, wobei $\begin{eqnarray*} t_a \cdot d = a \end{eqnarray*}$ und $\begin{eqnarray*} t_b \cdot b = b \end{eqnarray*}$ gilt?

12.07.2017, 11:36

marin_zi

Auf diesen Beitrag antworten »

Hallo

Zitat:

Original von IfindU
Das sind leider alles nur Zahlenbeispiele. Wenn dir sage, dass $\begin{eqnarray*} t:= t_a - t_b \end{eqnarray*}$ , kannst du nachrechnen, dass $\begin{eqnarray*} t \cdot d = a - b \end{eqnarray*}$ gilt, wobei $\begin{eqnarray*} t_a \cdot d = a \end{eqnarray*}$ und $\begin{eqnarray*} t_b \cdot b = b \end{eqnarray*}$ gilt?

Nein kann ich nicht (also ich meine ich kann dem nicht folgen) weil ich die Aufgabe bzw Frage nicht verstehe bzw was ich damit tun soll um zu zeigen
das damit die Aussage: $\begin{eqnarray*} \{ d \in \mathbb Z: d | a \text{ und } d | b \} = \{ d \in \mathbb Z: d | (a-b) \text{ und } d | b \} \end{eqnarray*}$ gilt.

$\begin{eqnarray*} t:= t_a - t_b \end{eqnarray*}$

$\begin{eqnarray*} t \cdot d = a - b \end{eqnarray*}$
$\begin{eqnarray*} t_a \cdot d = a \end{eqnarray*}$
$\begin{eqnarray*} t_b \cdot b = b \end{eqnarray*}$

Ich kann jetzt zwar einsetzten und herum formen oder was au ich immer.

$\begin{eqnarray*} t \cdot d = a - b \end{eqnarray*}$

$\begin{eqnarray*} t \cdot d = t_a \cdot d - t_b \cdot d \end{eqnarray*}$

Aber ich sehe nicht warum $\begin{eqnarray*} t \end{eqnarray*}$ bzw $\begin{eqnarray*} t \cdot d \end{eqnarray*}$ in jedem Fall ein durch $\begin{eqnarray*} d \end{eqnarray*}$ Teilbar Natürlich Zahl sein soll. Weil $\begin{eqnarray*} t \end{eqnarray*}$ für mich erstmal eine Unbekannte ist. Ich sehe das $\begin{eqnarray*} a,b \end{eqnarray*}$ ein durch $\begin{eqnarray*} d \end{eqnarray*}$ Teilbare Zahl sein muss da ich ja mit $\begin{eqnarray*} d \end{eqnarray*}$ mulitpliziert habe und da ich $\begin{eqnarray*} t_a,t_b,d \end{eqnarray*}$ frei gewählt habe und als Natürlich Zahl gewählt habe weiß ich das $\begin{eqnarray*} t_a,t_b \end{eqnarray*}$ und $\begin{eqnarray*} a,b \end{eqnarray*}$ Natürlich Zahlen sein müssen.

Aber was ist mit $\begin{eqnarray*} t \end{eqnarray*}$ bzw $\begin{eqnarray*} t \cdot d \end{eqnarray*}$ ? was sagt mir das es eine Natürlich Zahl die durch $\begin{eqnarray*} d \end{eqnarray*}$ teilbare ist, sein muss. $\begin{eqnarray*} t \cdot d \end{eqnarray*}$ ist durch $\begin{eqnarray*} d \end{eqnarray*}$ dividierbar aber wieso ist das Ergebnis nicht z.b eine Rationale Zahl ? also z.b 7.5 oder sonst was für eine Zahl ? Daher habe ich Schwierigkeiten dem zu folgen.

Wenn ich es aber so betrachte bzw umforme:

$\begin{eqnarray*} {a \over d} - {b \over d} = {t_D \over d} \end{eqnarray*}$

und weiß das ich mit $\begin{eqnarray*} t_a,t_b,d \end{eqnarray*}$ Natürlich Zahlen gewählt habe. Dann kürze ich das $\begin{eqnarray*} d \end{eqnarray*}$ aus der Gleichung. Und da die Zahlen immer vielfache von $\begin{eqnarray*} d \end{eqnarray*}$ sind ist es für mich einfacher zu sehen das alles Natürlich Zahlen sind die alle durch $\begin{eqnarray*} d \end{eqnarray*}$ Teilbar sind.

Also wenn ich zwei Natürlich Zahlen habe die durch $\begin{eqnarray*} d \end{eqnarray*}$ teilbar sind kann ich all das machen:

$\begin{eqnarray*} {a \over d} - {b \over d} = {t_D \over d} \end{eqnarray*}$

$\begin{eqnarray*} {a \over d} + {b \over d} = {t_D \over d} \end{eqnarray*}$

$\begin{eqnarray*} {a \over d} \cdot {b \over d} = {t_D \over d \cdot d} \end{eqnarray*}$

und habe immer als Ergebnis eine Natürlich Zahl die durch $\begin{eqnarray*} d \end{eqnarray*}$ teilbare ist. Zumindest so verstehe ich das.

Danke für die Geduld smile

smile

12.07.2017, 12:00

IfindU

Auf diesen Beitrag antworten »

Liegt das Problem gerade, dass du Teilbarkeit fuer natuerliche Zahlen kennst und ich von ganzen Zahlen $\begin{eqnarray*} \mathbb Z \end{eqnarray*}$ rede, oder verwendest du es als Abgrenzung zu den rationalen Zahlen?

Bei ersteren ist die zu zeigende Aussage falsch, wenn man nicht $\begin{eqnarray*} a \geq b \end{eqnarray*}$ fordert. Wenn man das hingegen fordert, kann man zeigen, dass die noetigen Elemente nicht nur ganz, sondern natuerlich sind.

12.07.2017, 12:49

marin_zi

Auf diesen Beitrag antworten »

Zitat:

Original von IfindU
Liegt das Problem gerade, dass du Teilbarkeit fuer natuerliche Zahlen kennst und ich von ganzen Zahlen $\begin{eqnarray*} \mathbb Z \end{eqnarray*}$ rede, oder verwendest du es als Abgrenzung zu den rationalen Zahlen?

Bei ersteren ist die zu zeigende Aussage falsch, wenn man nicht $\begin{eqnarray*} a \geq b \end{eqnarray*}$ fordert. Wenn man das hingegen fordert, kann man zeigen, dass die noetigen Elemente nicht nur ganz, sondern natuerlich sind.

Aja richtig ich meinte eigentlich die ganzen Zahlen. Also ich habe das als Abgrenzung zu den Rational Zahlen verwendet.

Klar wird es für mich erst wenn ich es so sehe

$\begin{eqnarray*} {a \over d} - {b \over d} = {t_D \over d} \end{eqnarray*}$

ansonsten bleibt für mich immer offen warum $\begin{eqnarray*} t,t \cdot d \end{eqnarray*}$ nicht auch rationale oder was weiß ich sein könnte.

12.07.2017, 12:56

IfindU

Auf diesen Beitrag antworten »

Also. Wir wissen, dass $\begin{eqnarray*} d \end{eqnarray*}$ eine ganze Zahl ist. Das ist eine der Voraussetzungen an $\begin{eqnarray*} d \end{eqnarray*}$ . Wir wissen, dass $\begin{eqnarray*} t_a, t_b \end{eqnarray*}$ ganze Zahlen sind. Diese gibt es naemlich aus der zweiten Voraussetzung an $\begin{eqnarray*} d \end{eqnarray*}$ , naemlich, dass $\begin{eqnarray*} d | a \end{eqnarray*}$ und $\begin{eqnarray*} d | b \end{eqnarray*}$ -- was eine kurze Schreibweise fuer "es gibt ganze Zahlen $\begin{eqnarray*} t_a,t_b \end{eqnarray*}$ mit $\begin{eqnarray*} t_a \cdot d = a \end{eqnarray*}$ und $\begin{eqnarray*} t_b \cdot d = b \end{eqnarray*}$ .

Nun definieren wir die Zahl $\begin{eqnarray*} t = t_a - t_b \end{eqnarray*}$ . Da $\begin{eqnarray*} t_a, t_b \end{eqnarray*}$ eine ganze Zahl war, so ist auch die Differenz eine ganze Zahl (ganze Zahlen sind unter der Addition abgeschlossen -- sogar eine Gruppe.) Wir rechnen nach, dass $\begin{eqnarray*} t \cdot d = a-b \end{eqnarray*}$ . Da es eine ganze Zahl $\begin{eqnarray*} t \end{eqnarray*}$ gibt, ist also nach Definition $\begin{eqnarray*} d | (a-b) \end{eqnarray*}$ . Damit gilt
$\begin{eqnarray*} ( d| a \text{ und } d| b) \implies (d | (a-b) \text{ und } d | b) \end{eqnarray*}$ .

Wenn man jetzt noch zeigen kann, dass $\begin{eqnarray*} ( d| (a-b) \text{ und }d| b) \implies (d | a \text{ und } d | b) \end{eqnarray*}$ hat man gezeigt, dass die Mengen meines ersten Posts gleich sind.

12.07.2017, 13:13

marin_zi

Auf diesen Beitrag antworten »

Zitat:

Original von IfindU
Nun definieren wir die Zahl $\begin{eqnarray*} t = t_a - t_b \end{eqnarray*}$ . Da $\begin{eqnarray*} t_a, t_b \end{eqnarray*}$ eine ganze Zahl war, so ist auch die Differenz eine ganze Zahl (ganze Zahlen sind unter der Addition abgeschlossen -- sogar eine Gruppe.)

Achnee stimmt geschockt

geschockt

geschockt

geschockt

Das ist ja total einfach. Big Laugh

Big Laugh

Das habe ich komplett übersehen. Von $\begin{eqnarray*} t \end{eqnarray*}$ ist ja schon bekannt das es eine ganze Zahl ist.

Zum 2ten brauche ich noch Zeit und überlege noch...

19.07.2017, 10:47

marin_zi

Auf diesen Beitrag antworten »

RE: ggT(a,b) = ggT(a - b,b)
Hallo

Jetzt muss ich nomal nachfragen.

Zitat:

Original von IfindU
Das ist keine Eigenschaft vom groessten gemeinsamen Teiler. Das ist eine Eigenschaft aller Teiler.

Also $\begin{eqnarray*} \{ d \in \mathbb Z: d | a \text{ und } d | b \} = \{ d \in \mathbb Z: d | (a-b) \text{ und } d | b \} \end{eqnarray*}$ . Man kann leicht ueberpruefen, das das stimmt. Und wenn die Teilermenge identitisch,besitzen beide das gleiche goresste Element - den ggT.

"Und wenn die Teilermenge identitisch"
Welche Teilermengen müssen identisch sein ? Oder muss es eine "echte Teilmenge" sein ?

Ich bin mir nicht sicher ob ich verstanden habe was eine identitisch Teilermenge ist. verwirrt

verwirrt

$\begin{eqnarray*} T_{12} = {1,2,3,4,6,12} \end{eqnarray*}$
$\begin{eqnarray*} T_{8} = {1,2,4,8} \end{eqnarray*}$

Also identisch wäre für mich genau die gleiche Teilermenge. Gleiche Anzahl an Elementen und die gleichen Zahlen.

Und hat nicht jede Zahl seine eigene Teilermenge ?

Grüße

19.07.2017, 12:22

IfindU

Auf diesen Beitrag antworten »

RE: ggT(a,b) = ggT(a - b,b)
Zumindest fuer die ganzen Zahlen ist
$\begin{eqnarray*} ggT(a,b) = \max \{ d \in \mathbb Z: d | a \text{ und } d | b \} \end{eqnarray*}$ und $\begin{eqnarray*} ggT(a-b,b) = \max \{ d \in \mathbb Z: d | (a-b) \text{ und } d | b \} \end{eqnarray*}$ .

Wenn man weiss, dass $\begin{eqnarray*} \{ d \in \mathbb Z: d | a \text{ und } d | b \} = \{ d \in \mathbb Z: d | (a-b) \text{ und } d | b \} \end{eqnarray*}$ ist, so stimmt insbesondere das Maximum der Mengen ueberein. Und das Maximum nennt man den ggT.

19.07.2017, 12:42

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von IfindU
Zumindest fuer die ganzen Zahlen ist
$\begin{eqnarray*} ggT(a,b) = \max \{ d \in \mathbb Z: d | a \text{ und } d | b \} \end{eqnarray*}$ .

Mit Ausnahme des Paares (a,b) = (0,0), aber den Sonderfall kann man ja auch extra betrachten.

19.07.2017, 13:41

IfindU

Auf diesen Beitrag antworten »

Danke HAL. Hatte den Spezialfall gar nicht auf dem Schirm. Interessant, dass (nach klassischer Definition vom ggT) gilt $\begin{eqnarray*} ggT(0,0) =0 \end{eqnarray*}$ .

1

Verwandte Themen