0 Daumen
1,5k Aufrufe

Aufgabe:

Ich soll eine allgemeine Definition aufstellen für den ggT von endlichen vielen ganzen Zahlen


Problem/Ansatz:

Mein Problem ist die Verallgemeinerung. Der ggT kann nur positiv sein und muss entweder 1 (teilerfremd) oder größer als 1 sein. Ich weiß nur nicht wie ich das ganze allgemein aufschreiben kann. Wäre super, wenn mir jemand helfen könnte oder mir einen Tipp gibt. Bin über jeden Ratschlag dankbar.


Liebe Grüße

Avatar von

Hi SoPäd25,

erstelle eine rekursive Definition. Versuch vielleicht mal als Inspiration den ggT von drei Zahlen zu bestimmen.

Gruß,

Hey Yakyu,

also einfach nur ggT (a,b,c) = (a,b,c)?

Ich soll nämlich anschließend die Identität ggT (a,b,c) = ggT (ggT (a,b),c) zeigen. Soweit ich das verstanden habe muss ich hier das Assoziativgesetz beweisen. Danach soll ein Beweis der Identität auf alle endlich vielen Zahlen erfolgen. Leider bauen alle Aufgaben aufeinander auf und ich bin total verwirrt.


Liebe Grüße

also einfach nur ggT (a,b,c) = (a,b,c)?

Das verstehe ich leider nicht.

Ich soll nämlich anschließend die Identität ggT (a,b,c) = ggT (ggT (a,b),c) zeigen

Ah ok, die Aufgabe führt dich zu dieser rekursiven Definition. Das heißt, du brauchst vorher eine rein formale Definition, sowas wie

Für \(k \in \mathbb{N}\) und \(n_1, \dots, n_k \in \mathbb{N}\) ist

\( \text{ggT}(n_1, \dots, n_k) := \max\{d \in \mathbb{N}; d | n_i \ ,\ i = 1, \dots, k \} \)

Damit kannst du dich dann an die obige Identität trauen. Dabei musst du zeigen, dass die Zahl die hinter beiden Seiten der Gleichung steht jeweils gleich ist.

Es handelt sich dabei übrigens nicht um das Assozitativgesetz, dieses würde eher so aussehen:

\( \text{ggT}(\text{ggT}(a,b),c) = \text{ggT}(a,\text{ggT}(b,c))\)

In der Vorlesung haben wir zwei Zahlen als ggT (a,b) = (a,b) definiert. Da in Aufgabenteil b) das Assoziativgesetz gezeigt werden soll, was aus 3 Zahlen besteht, dachte ich, dass ggT (a,b,c) = (a,b,c) eventuell ausreichend ist, da auch Teil b) nochmal im Teil c) auf endlich viele Zahlen verallgemeinert und bewiesen werden soll. Aber da täusche ich mich wahrscheinlich. Ich stehe hier wirklich auf dem Schlauch und weiß nicht weiter. Vielen lieben Dank aber schonmal.

Liebe Grüße

Und wie habt ihr (a,b) definiert? Das ist grundsätzlich erstmal nur ein Tupel.

In b) soll nicht das Assoziativgesetz gezeigt werden (s.o.) sondern eine andere Form der Definition von ggT für 3 Zahlen.

Also ganz konkreter Wortlaut ist: Für a,b Elemente in Z heißen die Elemente aus Z(a) geschnitten T(b) gemeinsame Teiler von ab. Das größte Element von T(a) geschnitten T(b) heißt größter gemeinsamer Teiler von ab.

Symbolisch: ggT (a,b) = (a,b)

Mehr zur Definition haben wir nicht, d.h. auch (a,b) ist nicht weiter definiert.

Oh okay, hatte grade vor lauter Suchen den Rest überlesen.

Ich gehe davon aus, dass T(a) die Menge der Teiler der ganzen Zahl a ist.

Dann ist

Für a,b Elemente in Z heißen die Elemente aus T(a) geschnitten T(b) gemeinsame Teiler von a und b. Das größte Element von T(a) geschnitten T(b) heißt größter gemeinsamer Teiler von a und b.

Deine Definition.

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

Das ist reine Notation und sagt für sich selbst nicht aus, ich hoffe du siehst den Unterschied. Deswegen solltest du den allgemeinen Fall mal in der Form deiner Definition abarbeiten. Sprich du suchst ja den größten gemeinsamen Teiler von \(k\) (verschiedenen) ganzen Zahlen. Und dieser ist das größte Element des Schnitts der Teilermengen dieser Zahlen.

Genau T(a) ist die Teilermenge von a. Diese Notation wurde uns als Tipp gegeben, um auf a) zu kommen, was ich nicht verstanden habe, aber du hat oben schon sehr viel dazu geschrieben und das habe ich soweit verstanden.

Meintest du bei b), dass ich zeigen muss, dass ggT (a,b,c) =x und ggT (ggT (a,b),c) = x ?

ggT (a,b,c) =x und ggT (ggT (a,b),c) = x

Ja genau! Wenn du das gezeigt hast, hast du nachgewiesen, dass man den ggT für drei Zahlen auch durch den ggT von zwei Zahlen sinnvoll (rekursiv) definieren kann.

(bei c) musst du die Gleichung nur verallgemeinern, siehe Antwort von Roland).

Vielen lieben Dank für deine schnellen Antworten und deine Zeit. Ich versuche das jetzt einfach mal.

2 Antworten

0 Daumen

Die Definition muss rekursiv sein. Zunachst legen wir fest: ggT2(ai, i von 1 bis 2) oder allgemein: ggTn(ai, i von 1 bis n).

Dann definieren wir ggTn(ai, i von 1 bis n):=ggTn(ggTn-1(ai, i von 1 bis n-1),an).

Avatar von 123 k 🚀

Hallo Roland,

ich verstehe alles bis zum Punkt allgemein. Wieso müssen wir noch einen Schritt weiter gehen mit ggTn (ggTn-1 (ai, i von 1 bis n-1), an)? Das verwirrt mich etwas. Könntest du das nochmal genauer erläutern?

Wie auch oben bereits kommentiert soll ich nämlich anschließend die Identität ggT (a,b,c) = ggT (ggT (a,b),c) zeigen, was natürlich mit einer kürzeren Definition einfacher wäre. Für den ggT von zwei Zahlen haben wir in der Vorlesung definiert ggT (a,b) = (a,b). Daher dachte ich, dass eventuell ggT (a,b,c) = (a.b,c) ausreichend ist, was aber leider auch nicht endlich viele Zahlen einschließt. Zum Schluss soll ich nämlich auch die oben genannte Identität auf endlich viele Zahlen verallgemeinern und beweisen. Die Mathebücher helfen mir hierbei leider auch nicht. Vielleichst hast du noch einen Tipp?

Liebe Grüße

Eure Definition aus der Uni ggT (a,b) = (a,b)  verstehe ich nicht. Aber gehen wir mal davon aus, dass ggT (a,b) irgendwie definiert ist, dann ist ggT (a,b,c) = ggT(ggT(a,b),c) und ggT (a,b,c,d) = ggT(ggT(a,b,c),d). Und immer so weiter. Um diesen Vorgang auszudrücken, habe ich die Schreibweise ggTn erfunden, die den ggT von n Zahlen beschreibt. In dieser Schreibweise beschreibt ggTn-1 den ggT von n-1 Zahlen. Und ggTn =ggT(ggTn-1, an) fügt dann dem gefundenen ggTn-1 aus n-1 Zahlen eine Zahl an hinzu.

Ok super danke, dann verstehe ich, was damit gemeint ist.

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community