Wie bestimme ich allgemein den ggT von endlich vielen ganzen Zahlen?

Question

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

Comments

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.

Answer 1

https://de.wikipedia.org/wiki/Eulersche_Phi-Funktion

Answer 2

Die Definition muss rekursiv sein. Zunachst legen wir fest: ggT₂(a_i, i von 1 bis 2) oder allgemein: ggT_n(a_i, i von 1 bis n).

Dann definieren wir ggT_n(a_i, i von 1 bis n):=ggT_n(ggT_n-1(a_i, i von 1 bis n-1),a_n).

Comments

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 ggT_n erfunden, die den ggT von n Zahlen beschreibt. In dieser Schreibweise beschreibt ggT_n-1 den ggT von n-1 Zahlen. Und ggT_n =ggT(ggT_n-1, a_n) fügt dann dem gefundenen ggT_n-1 aus n-1 Zahlen eine Zahl a_n hinzu.

---

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