Zum Hauptinhalt springen
CalcMax

GGT-Rechner

Ergebnis

12

Größter gemeinsamer Teiler

Gemeinsame Teiler
1, 2, 3, 4, 6, 12

Ein größter gemeinsamer Teiler ist die größte ganze Zahl, die jede Zahl einer Liste ohne Rest teilt. Für 24, 36 und 60 ist das die 12: Nichts Größeres teilt alle drei, und jede Zahl, die alle drei teilt, ist ein gemeinsamer Teiler von ihnen. Diese Seite druckt beide Hälften dieser Antwort, weil die größte allein leicht zu behaupten und schwer nachzuprüfen ist, während die vollständige Liste zeigt, woher sie kommt. Die Liste zeigt außerdem, was nicht zählt: 1, 2, 3, 4, 6 und 12 sind gemeinsame Teiler aller drei, die 8 und die 9 dagegen teilen nur zwei von ihnen. Es gibt drei Wege zur Antwort, und alle drei sind es wert, gekannt zu werden. Der erste ist, die Teiler jeder Zahl aufzuschreiben und den größten zu behalten, den sie gemeinsam haben — das ist es, was die Tabelle unten für 24, 36 und 60 tut. Der zweite ist, jede Zahl in ihre Primfaktorzerlegung zu zerlegen und nur die Primzahlen zu behalten, über die sie sich einig sind, so oft wiederholt, wie sie sich einig sind: 24 ist 2³ × 3, 36 ist 2² × 3², und 60 ist 2² × 3 × 5, also teilen alle drei die 2² und eine 3, und 2² × 3 ist 12. Die Primfaktorzerlegung ist die Methode der Wahl, wenn die Zahlen groß, aber zerlegbar sind, weil sie erklärt, warum die Antwort die ist, die sie ist. Der dritte ist das Verfahren, das euklidischer Algorithmus heißt und wiederholt die größere von zwei Zahlen durch ihren Rest bei der Division durch die kleinere ersetzt: Für 1071 und 462 ist das 1071 → 147 → 21, und der letzte Rest, der nicht null ist, ist die Antwort, 21. Er braucht überhaupt keine Zerlegung, und deshalb ist er die Methode, die auf Zahlen skaliert, die man nicht mehr mit einem Blick zerlegen kann. Zwei Zahlen, deren einziger gemeinsamer Teiler die 1 ist, heißen teilerfremd, und ihr größter gemeinsamer Teiler ist 1 — 9 und 20 sind teilerfremd, und ebenso zwei beliebige aufeinanderfolgende ganze Zahlen. Gebraucht wird der Teiler, um einen Bruch auf seinen kleinsten Nenner zu bringen: Zähler und Nenner von 24/36 durch 12 zu teilen ergibt 2/3, dieselbe Zahl mit dem kleinstmöglichen Nenner geschrieben.

Die Teiler und Primfaktorzerlegungen von 24, 36 und 60, der Standardeingabe

ZahlPrimfaktorzerlegungTeiler
242^3 * 31, 2, 3, 4, 6, 8, 12, 24
362^2 * 3^21, 2, 3, 4, 6, 9, 12, 18, 36
602^2 * 3 * 51, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60

Lesen Sie die Teilerspalte von oben nach unten, und die drei gemeinsamen Zahlen sind die, die in allen drei Zeilen vorkommen: 1, 2, 3, 4, 6 und 12. Die größte von ihnen ist die Antwort. Die Zerlegungsspalte sagt dasselbe ein zweites Mal, und das zweite Mal ist das, was skaliert: Die gemeinsamen Primzahlen sind 2² und 3, und 2² × 3 ist 12. Beachten Sie, dass der gemeinsame Teil die kleinste Potenz jeder gemeinsamen Primzahl ist und nicht die größte — die 36 hat 3², die 24 aber nur 3¹, und der Teiler muss auch die 24 teilen, trägt also eine einzige 3. Beachten Sie außerdem, dass die 60 eine Primzahl mitbringt, die die anderen gar nicht haben, die 5, und die fällt einfach aus der Antwort heraus: Ein Teiler muss jede Zahl der Liste teilen, eine Primzahl, die in einer einzigen von ihnen fehlt, fehlt also auch in der Antwort. Die Tabelle folgt nicht den Zahlen, die Sie eingetippt haben — die Anzeige oben beantwortet die, diese hier zeigt die drei Methoden an einem Beispiel.

Formel

24 = 2³ × 3, 36 = 2² × 3², 60 = 2² × 3 × 5 ⇒ ggT(24, 36, 60) = 2² × 3 = 12, und die gemeinsamen Teiler aller drei sind 1, 2, 3, 4, 6, 12

24, 36, 60
Die Zahlen, die verglichen werden, zwei bis zehn Stück, jede eine ganze Zahl von 1 bis 1.000.000. Getrennt werden sie durch Leerzeichen, Kommas oder Semikolons, 24 36 60 und 24, 36, 60 sind also dieselbe Eingabe. Ein Dezimaltrennzeichen oder ein Bruchstrich wird abgelehnt statt gerundet, und ebenso die 0 — für ggT(0, 0) gibt es keine einheitliche Vereinbarung, und diese Seite wählt keine für Sie aus
2³ × 3
Die Primfaktorzerlegung von 24: drei Zweien und eine Drei. Jede ganze Zahl über 1 hat genau eine solche Zerlegung, und das ist es, was die zweite Methode möglich macht
2² × 3
Der Teil, über den sich alle drei Zerlegungen einig sind: zwei Zweien und eine Drei, also 4 × 3 = 12. Die Regel ist, von jeder gemeinsamen Primzahl die kleinste Potenz zu nehmen und nicht die größte — der Teiler muss alle Zahlen der Liste teilen, kann also nie mehr sein, als die knappste von ihnen zulässt
1, 2, 3, 4, 6, 12
Alle gemeinsamen Teiler, aufsteigend. Der letzte ist der größte gemeinsame Teiler, und die Liste ist die Probe: 12 teilt 24, 36 und 60 ohne Rest, und der nächste Teiler darüber, die 18, teilt nur die 36
ggT(a, b, c) = ggT(ggT(a, b), c)
Wie mehr als zwei Zahlen behandelt werden: zwei auf einmal, wobei das laufende Ergebnis in die nächste Zahl hineingefaltet wird. Das ist keine eigene Methode, sondern die Zwei-Zahlen-Methode wiederholt angewendet, und deshalb liefert die Seite für drei Zahlen dieselbe Antwort wie für jedes Paar, mit dem man anfängt
teilerfremd
Der Name für ein Paar, dessen einziger gemeinsamer Teiler die 1 ist, dessen größter gemeinsamer Teiler also 1 ist. 9 und 20 sind teilerfremd, obwohl keine der beiden Zahlen eine Primzahl ist, und zwei aufeinanderfolgende ganze Zahlen sind es immer. Ein Teiler von 1 ist eine vollständige Antwort und kein Fehlschlag

Einen Bruch auf seinen kleinsten Nenner zu bringen ist der Alltagsnutzen: 24/36 ist 2/3, sobald Sie beide Teile durch 12 teilen, und derselbe Schritt ist das Erste, was jede Bruchseite hier tut. Ein Rezept oder eine Zeichnung auf das kleinste ganzzahlige Verhältnis herunterzurechnen ist dieselbe Rechnung in anderer Kleidung — eine Mischung, die als 24 : 36 : 60 geschrieben ist, ist dieselbe wie 2 : 3 : 5, und die zweite Fassung ist die, die auf ein Etikett passt. Im Rechenunterricht wird der Teiler direkt erfragt, und die gedruckte Liste der gemeinsamen Teiler ist der Rechenweg: Sie zeigt, dass die Antwort durch Vergleichen von Teilern gefunden wurde und nicht geraten. Zwei weitere Stellen, an denen er auftaucht: Ein Rechteck mit möglichst großen quadratischen Fliesen zu belegen ist eine ggT-Frage in Verkleidung, und die Antwort ist die Fliesengröße. Und in der Zahlentheorie ist die Tatsache, dass zwei Zahlen teilerfremd sind, die Bedingung, unter der mehrere andere Ergebnisse erst funktionieren, darunter das hinter der RSA-Verschlüsselung — ein Modul ist nur dann sicher, wenn es zu dem Exponenten teilerfremd ist, mit dem es verwendet wird. Wenn die Zahlen unhandlich sind, etwa 1071 und 462, hört das Zerlegen von Hand auf, praktikabel zu sein, und der euklidische Algorithmus übernimmt; die Beispiele dieser Seite zeigen beide Wege mit derselben 21. Wer den Rechenweg Zeile für Zeile sehen will und nicht nur die Antwort, ist beim Euklidischer-Algorithmus-Rechner richtig, der jede Runde ausschreibt; die Zerlegung selbst übernimmt der Primfaktorzerlegung-Rechner; und Brüche kürzt der Brüche-kürzen-Rechner direkt, ohne Ihnen die Teilerliste zu zeigen.

Rechenbeispiele

  1. Der größte gemeinsame Teiler von 24, 36 und 60

    1. Teiler von 24: 1, 2, 3, 4, 6, 8, 12, 24
    2. Teiler von 36: 1, 2, 3, 4, 6, 9, 12, 18, 36
    3. Teiler von 60: 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60
    4. Behalten Sie die, die alle drei Listen enthalten: 1, 2, 3, 4, 6, 12
    5. Der größte davon ist die 12, der größte gemeinsame Teiler ist also 12

    Die Standardeingabe und die, die die Tabelle unten vollständig durchgeht. Über die Primfaktorzerlegung statt über die Listen: 24 ist 2³ × 3, 36 ist 2² × 3², 60 ist 2² × 3 × 5, alle drei teilen die 2² und eine 3, und 2² × 3 ist 12. Die Liste der gemeinsamen Teiler ist der Teil, den man behalten sollte — sie ist die einzige Ausgabe, die zeigt, dass die Antwort die größte ist und nicht bloß eine gemeinsame: Die 8 und die 9 teilen jeweils zwei der drei Zahlen, aber nicht alle.

  2. Unhandliche Zahlen: 1071 und 462

    1. 1071 ÷ 462 = 2 Rest 147
    2. 462 ÷ 147 = 3 Rest 21
    3. 147 ÷ 21 = 7 Rest 0 — der Rest ist bei null angekommen, also Schluss
    4. Der letzte Rest ungleich null ist 21, der größte gemeinsame Teiler ist also 21
    5. Probe über die Zerlegung: 1071 = 3 × 7 × 51 und 462 = 2 × 3 × 7 × 11, der gemeinsame Teil ist also 3 × 7

    Dieses Paar ist der Grund, warum der euklidische Algorithmus überhaupt auf der Seite steht: Keine der beiden Zahlen lässt sich auf einen Blick zerlegen, und die Teiler von Hand aufzulisten wäre langsam und fehleranfällig. Vier Divisionen entscheiden es. Die 21 ist zugleich die größte Zahl, die beide teilt, und die gemeinsame Liste ist kurz — 1, 3, 7, 21 —, was meistens das Zeichen dafür ist, dass zwei Zahlen wenig miteinander zu tun haben.

  3. Teilerfremde Zahlen: 9 und 20

    1. Teiler von 9: 1, 3, 9
    2. Teiler von 20: 1, 2, 4, 5, 10, 20
    3. Der einzige Teiler, den beide Listen gemeinsam haben, ist die 1
    4. Der größte gemeinsame Teiler ist damit 1

    Eine Antwort von 1 ist eine echte Antwort und kein Fehlschlag — die beiden Zahlen sind teilerfremd. Das passiert immer, wenn die Zahlen keine einzige Primzahl gemeinsam haben, und es ist häufig: Zwei aufeinanderfolgende ganze Zahlen sind immer teilerfremd, und ebenso eine Primzahl mit jeder Zahl, die kein Vielfaches von ihr ist. Auf dieser Seite kommt ein teilerfremdes Paar mit der kürzestmöglichen Liste gemeinsamer Teiler zurück, einer einzigen 1.

  4. Eine Zahl neben sich selbst: 36 und 36

    1. Teiler von 36: 1, 2, 3, 4, 6, 9, 12, 18, 36
    2. Beide Einträge der Liste sind dieselbe Zahl, die beiden Teilerlisten sind also identisch
    3. Der größte gemeinsame Teiler ist die 36 selbst

    Das obere Ende dessen, was die Antwort sein kann: Der größte gemeinsame Teiler einer Liste kann nie größer sein als die kleinste Zahl darin, und er erreicht diese Grenze genau dann, wenn die kleinste Zahl alle anderen teilt. Eine Zahl in der Eingabe zu wiederholen ändert nichts — der Teiler von 36 und 36 ist 36, derselbe wie der Teiler einer Liste mit einem einzigen Eintrag.

Einschränkungen

Jede Zahl muss eine ganze Zahl von 1 bis 1.000.000 sein, und es müssen zwischen zwei und zehn sein. Die Null wird abgelehnt, und das ist eine Entscheidung und kein Versehen: ggT(0, 5) ist nach einer verbreiteten Vereinbarung 5 und nach anderen undefiniert, und ggT(0, 0) ist in manchen Lehrbüchern 0 und im Rest gar nicht definiert. Eine dieser Antworten zu drucken wäre für einen Leser falsch, der einer anderen Vereinbarung folgt, deshalb fragt die Seite nach positiven Zahlen. Negative Zahlen werden aus demselben Grund abgelehnt — der Teiler von −24 und 36 ist in den meisten Darstellungen 12, aber die Vorzeichenregeln sind eine eigene Vereinbarung, die diese Seite nirgends nennt. Dezimalzahlen und Brüche werden abgelehnt statt gerundet: Ein größter gemeinsamer Teiler ist eine Aussage darüber, dass ganze Zahlen ganze Zahlen teilen, und 2,5 ÷ 1,25 geht ohne Rest auf, was die Antwort sinnlos machen würde. Als Trennzeichen sind Leerzeichen, Kommas oder Semikolons erlaubt, gemischt oder nicht; alles andere wird als Teil einer Zahl gelesen und macht die Eingabe unlesbar. Die Referenztabelle unten steht fest bei 24, 36 und 60 und folgt nicht dem, was Sie eingetippt haben — die Anzeige beantwortet Ihre Zahlen, die Tabelle zeigt die Methode. Wiederholte Einträge sind erlaubt und ändern nichts. Die Antwort ist exakt und nie gerundet: Jeder Wert auf dieser Seite ist eine ganze Zahl, die weit innerhalb dessen liegt, was eine Maschine genau hält.

Häufige Fragen

Wie finde ich den größten gemeinsamen Teiler von Hand?
Notieren Sie die Teiler jeder Zahl und nehmen Sie den größten, den alle gemeinsam haben. Für 24, 36 und 60 enden diese Listen bei 12, der größte gemeinsame Teiler ist also 12. Der schnellere Weg für größere Zahlen ist der euklidische Algorithmus: Teilen Sie die größere durch die kleinere, ersetzen Sie die größere durch den Rest und wiederholen Sie das, bis der Rest null ist — für 1071 und 462 sind das vier Divisionen, und die Antwort ist 21. Beide Wege liefern dieselbe Zahl, und beide sind in den Beispielen oben gezeigt.
Was bedeutet es, wenn der ggT 1 ist?
Dass die Zahlen teilerfremd sind, was eine normale Antwort ist und kein Zeichen dafür, dass etwas schiefgelaufen wäre. 9 und 20 haben überhaupt keine gemeinsame Primzahl, die 1 ist also die einzige Zahl, die beide teilt. Das kommt häufig vor: Zwei aufeinanderfolgende ganze Zahlen sind immer teilerfremd, und ebenso eine Primzahl mit allem, was kein Vielfaches von ihr ist. Die Liste der gemeinsamen Teiler besteht in diesem Fall aus einer einzigen 1.
Warum lehnt die Seite 0 und negative Zahlen ab?
Weil die Antwort von einer Vereinbarung abhinge, die diese Seite nicht nennt. ggT(0, 5) ist in vielen Lehrbüchern 5 und in anderen undefiniert, und ggT(0, 0) ist in manchen Darstellungen 0 und im Rest überhaupt nicht definiert. Negative Zahlen bringen einen eigenen Satz Vorzeichenregeln mit. Statt sich eine Vereinbarung auszusuchen und sie stillschweigend zu drucken, verlangt die Seite ganze Zahlen ab 1, wo alle Quellen übereinstimmen.
Wie funktioniert die Methode über die Primfaktorzerlegung?
Zerlegen Sie jede Zahl in Primzahlen und behalten Sie dann die Primzahlen, die in allen Zahlen vorkommen, jeweils in der kleinsten Potenz. Für 24, 36 und 60 sind das 2² und 3, die Antwort ist also 12. Dass es die kleinste Potenz sein muss, liegt daran, dass der Teiler jede Zahl der Liste teilen muss: Die 36 hat 3², die 24 aber nur eine 3, eine zweite 3 würde die Division der 24 also zerstören. Die Zerlegung ist bei unhandlichen Zahlen langsamer als der euklidische Algorithmus, dafür erklärt sie die Antwort.
Kann die Antwort größer sein als die kleinste Zahl der Liste?
Nein. Ein gemeinsamer Teiler einer Liste muss die kleinste Zahl darin teilen, kann sie also nie überschreiten, und der Teiler erreicht diese Grenze genau dann, wenn die kleinste Zahl alle anderen teilt. Der Teiler von 36 und 36 ist 36, und der Teiler von 12, 24 und 36 ist 12. Kleiner als 1 ist er ebenfalls nie, da die 1 jede ganze Zahl teilt.
Wofür braucht man den größten gemeinsamen Teiler?
Einen Bruch auf seinen kleinsten Nenner zu bringen ist der häufigste Fall: Beide Teile von 24/36 durch 12 zu teilen ergibt 2/3, denselben Wert mit dem kleinstmöglichen Nenner. Ein Verhältnis herunterzurechnen ist derselbe Schritt — 24 : 36 : 60 ist dieselbe Mischung wie 2 : 3 : 5. Und dass zwei Zahlen teilerfremd sind, was dasselbe ist wie ein Teiler von 1, ist die Bedingung, die mehrere Ergebnisse der Zahlentheorie brauchen, darunter das hinter der RSA-Verschlüsselung.

Quellen

Verwandte Rechner

Brüche-kürzen-RechnerKürzt einen Bruch vollständig und zeigt den Teiler.Gleichwertige-Brüche-RechnerBrüche, die einem gegebenen Bruch entsprechen, bis zum Limit.KGV-RechnerDie ersten vier gemeinsamen Vielfachen mehrerer Zahlen.Bruch-RechnerRechnet mit Brüchen und kürzt das Ergebnis.Euklidischer-Algorithmus-RechnerGGT nach dem euklidischen Algorithmus, Schritt für Schritt.Primfaktorzerlegung-RechnerPrimfaktorzerlegung einer Zahl, mit Potenzschreibweise.