Den größten gemeinsame Teiler zweier natürlicher Zahlen zu kennen ist insbesondere dann von Nutzen, wenn es darum geht Brüche effizient zu kürzen. Wir zeigen dir in diesem Blogartikel drei verschiedene Möglichkeiten wie man den größten gemeinsamen Teiler, auch ggT genannt, finden kann und erklären welche Stärken und Schwächen die unterschiedlichen Rechenvorschriften mit sich bringen.
Bist du nicht auf der Suche nach Erklärungen sondern nach Aufgaben zum Üben? Dann springe gleich zu unserem Aufgabengenerator und drucke dir kostenlos so viele Übungsblätter als PDF 📃 aus wie du rechnen kannst.
Der Begriff “größter gemeinsamer Teiler” zweier natürlicher Zahlen beschreibt bereits recht gut über welche Eigenschaften definiert ist. Um zu bestimmen benötigen wir zum einen die Teilermengen der beiden involvierten natürlichen Zahlen und um daraus die gemeinsame Teilermenge zu bestimmen. Die Menge sollten nun alle Zahlen enthalten die sowohl Teiler von als auch Teiler von sind.
Nehmen wir nun noch das Maximum der gemeinsame Teilermenge, so erhalten wir den größten gemeinsamen Teiler von und
Um das ganze nicht zu theoretisch zu machen, schauen wir uns folgendes Beispiel an. Wir suchen den größten gemeinsamen Teiler von und . Folgende Zahlen sind Teiler von bzw. von :
Wir sehen bereits, dass die Teiler sowohl Teiler von als auch sind. Da wir an den größten gemeinsamen Teiler interessiert sind, folgt
Oftmals wird im Zusammenhang mit dem größten gemeinsamen Teiler auch das kleinste gemeinsame Vielfache (kgV) diskutiert. Ähnlich wie beim ggT wird der kgV beim Rechnen mit Brüchen verwendet. Während der ggT eine hilfreiche Rechenvorschrift beim Kürzen von Brüchen darstellt, erleichtert der kgV das Erweitern und damit das Addieren und Subtrahieren von Brüchen.
Folgendes Vorwissen solltest du bereits mitbringen, um den größten gemeinsamen Teiler zweier natürlicher Zahlen bestimmen zu können. Solltest du mit einem der Themen noch Schwierigkeiten haben, findest du auf unserer Seite nützliche Informationen und kannst dir natürlich kostenlos so viele Übungsaufgaben ausdrucken wie du rechnen kannst.
Der größte gemeinsame Teiler zweier natürlicher Zahlen lässt sich mit Hilfe ihrer Teilermengen bestimmen. Auch wenn diese Verfahren für große Zahlen zunehmend ineffizienter wird, ist diese Rechenvorschrift ein intuitiver Zugang, um sich mit dem abstrakten Konzept des ggT vertraut zu machen.
Wir erklären das Vorgehen Schritt für Schritt anhand des Beispiels und .
Wir starten mit der Bestimmung der Teilermenge für die erste natürliche Zahl :
Mit Hilfe der wichtigsten Teilbarkeitsregeln ist die Teilermenge schnell bestimmt. Beachte, dass du zur Bestimmung der Teilermenge die Probedivision nur bis maximal durchführen musst. Falls du eine Auffrischung hierzu brauchst, liest dir unseren Artikel zur Probedivision durch.
Im zweiten Schritt verfahren wir mit analog wie in Schritt 1 und bestimmen die Teilermenge:
Nun bildest du aus den beiden vorherigen Schritten die Schnittmenge der jeweiligen Teilermengen
Wenn du beide Mengen untereinander schreibst oder gemeinsame Teiler farblich markierst, kannst du die Schnittmenge einfach ablesen.
Der letzte Schritt ist dann nur noch das Maximum (also die größte Zahl) aus der Schnittmenge abzulesen. Wenn du die Schnittmenge der Größe nach aufsteigend sortiert hast, ist es die letzte Zahl in der Schnittmenge.
Die Primfaktorzerlegung ist eine zweite Methode mit deren Hilfe du ebenfalls den größten gemeinsamen Teiler zweier natürlicher Zahlen bestimmen kannst. Wir schauen uns dazu das gleiche Beispiel aus Methode 1 an, um Schritt für Schritt die Rechenvorschrift zu erklären:
Das Ergebnis der Primfaktorzerlegung für und schreibst du am Besten direkt untereinander.
Um den ggT zu erhalten, musst du nun alle Primfaktoren bestimmen, die sowohl Teil der Primfaktorzerlegung von als auch von sind.
Die gefundenen gemeinsamen Primfaktoren werden nun miteinander multipliziert und liefern den gesuchten größten gemeinsamen Teiler.
Achte darauf, dass du die Vielfachheit der Primfaktoren berücksichtigst. Kommt ein Primfaktor in beiden natürlichen Zahlen mehrfach vor, so muss dieser Primfaktor für die Bestimmung des größten gemeinsamen Teilers auch mehrfach multipliziert werden.
Die beiden zuvor vorgestellten Rechenverfahren eignen sich nur solange die beiden natürlichen Zahlen, für die ein größter gemeinsamer Teiler gesucht wird, nicht zu groß sind. In solchen Fällen ist der Euklidische Algorithmus gegenüber der Primfaktorzerlegung sowie der Bestimmung durch Teilermengen vorzuziehen. Dabei macht sich der Euklidische Algorithmus folgende Eigenschaft zu Nutze
,
indem die rekursiv Anwendung der obigen Gleichung solange durchgeführt wird, bis sich der finale Term nicht weiter reduzieren lässt. Damit vereinfacht sich das Problem darauf eine endliche Anzahl an Divisionen durch zu führen, was insbesondere für Computer keine große Herausforderung darstellt. Wir erklären das Verfahren an dem konkreten Beispiel :
Führe in der ersten Zeile die Division mit den beiden natürlichen Zahlen aus der Aufgabenstellung durch. Dabei wird die größere Zahl durch die kleinere geteilt.
Notiere auch den Rest der Divisionsaufgabe, da dieser im nächsten Schritt benötigt wird.
Aus den Ergebnissen aus Schritt 1 und mit Hilfe der rekursiven Formel oben, ergibt sich nun eine ggT-Aufgabe mit zwei neuen natürliche Zahlen. Zum einen die kleinere Zahl der ursprünglichen ggT-Aufgabe und zum anderen der Rest der Divisionsaufgabe.
Dazu schreiben wir in unserem Beispiel in die nächste Zeile fort (in hellblau markiert) und teilen nun durch , dem Rest der vorherigen Divisionsaufgabe (in lila markiert).
Die Division ergibt wieder einen Rest verschieden von Null, so dass wir die nächste ggT-Aufgabe wie in Schritt 2 bestimmen können.
Der Dividend wird nun in die 3. Zeile fortgeschrieben (in hellblau markiert) und durch den Rest der vorherigen Divisionsaufgabe geteilt (in lila markiert).
Wir wiederholen nun Schritt 2 bzw Schritt 3 solange die Divisionsaufgabe keinen Rest zurückliefert.
Die letzte Iterationsschleife formuliert eine Divisionsaufgabe die keinen Rest hat (bzw. den Rest Null).
Damit sind wir am Ende des Algorithmus angelegt und können das Ergebnis in der letzten Zeile ablesen.
Das Ergebnis der ursprünglichen Aufgaben kann mit der letzten Zeile anhand des Divisors abgelesen werden.
Somit ergibt .
Für die Aufgabe einen größten gemeinsamen Teiler für mehr als zwei natürliche Zahlen zu finden können wir die Methoden, die wir in diesem Kapitel vorgestellt haben, anwenden. Da folgendes für den größten gemeinsamen Teiler gilt
,
besteht die Aufgabe also darin, die Bestimmung des ggT mehrfach durch zu führen, wobei die Reihenfolge der Bestimmung dabei keine Rolle spielt.
Würden wir z.B. die Aufgabe bekommen, den ggT der drei natürlichen Zahlen zu bestimmen, könnten wir zuerst
wie gehabt berechnen, um im Anschluss das Ergebnis dieser Berechnung für die zweite Bestimmung
zu verwenden. Damit ist .
Falls du eine Auffrischung benötigst wie Teilermengen gebildet werden, dann schau dir unser Video dazu an