ggT-Rechner: größter gemeinsamer Teiler mit Rechenweg
MathematikWählen Sie, für wie viele Zahlen Sie den ggT brauchen, und tragen Sie sie ein. Der Rechner nennt den größten gemeinsamen Teiler und zeigt die Divisionen des euklidischen Algorithmus und die Primfaktoren, damit Sie den Weg nachrechnen können.
Rechenweg
ggT(12, 18) = 6
- Zerlegen Sie 12 und 18 in Primfaktoren, wie die Tabelle unten zeigt.
- Multiplizieren Sie die gemeinsamen Primfaktoren, jeden mit seinem kleinsten Exponenten: 2 · 3. Gibt es keinen, ist das Produkt 1.
- Das Produkt ist der größte gemeinsame Teiler: 6.
- Der euklidische Algorithmus führt zum selben Ergebnis: Der letzte Divisor, bei dem der Rest 0 bleibt, ist 6.
Sobald alle Eingaben gültig sind, sehen Sie hier jeden Rechenschritt.
Formel
- ggT
- größter gemeinsamer Teiler, die größte Zahl, die alle gegebenen Zahlen teilt
- pi
- die Primzahlen, die in allen Zahlen als Faktor vorkommen
- mi
- der kleinste Exponent, mit dem die jeweilige Primzahl in den Zerlegungen steht
- q, r
- Quotient und Rest der Division von a durch b, wobei r kleiner als b ist
- kgV
- kleinstes gemeinsames Vielfaches der beiden Zahlen
So funktioniert der Rechner
Der größte gemeinsame Teiler (ggT) mehrerer ganzer Zahlen ist die größte Zahl, durch die sich alle ohne Rest teilen lassen. Die Teiler von 12 sind 1, 2, 3, 4, 6 und 12, die von 18 sind 1, 2, 3, 6, 9 und 18. Gemeinsam sind 1, 2, 3 und 6, die größte davon ist 6, also gilt ggT(12, 18) = 6. Ist der ggT gleich 1, heißen die Zahlen teilerfremd. Der Rechner nimmt zwei, drei oder vier positive ganze Zahlen bis eine Billion und zeigt beide klassischen Wege zum Ergebnis.
Der erste Weg ist die Primfaktorzerlegung. Sie schreiben jede Zahl als Produkt von Primzahlen und multiplizieren die Primfaktoren, die in allen Zahlen vorkommen, jeden mit seinem kleinsten Exponenten. Für 12 = 2² · 3 und 18 = 2 · 3² bleiben 2 und 3, jeweils mit der Potenz 1, also 2 · 3 = 6. Die Tabelle unter dem Ergebnis zeigt die Zerlegung jeder eingegebenen Zahl.
Der zweite Weg ist der euklidische Algorithmus, den Euklid um 300 v. Chr. in seinen Elementen beschrieben hat. Er braucht keine Primfaktoren: Sie teilen die größere Zahl durch die kleinere, dann den Divisor durch den Rest, und so weiter, bis der Rest 0 ist. Der letzte Divisor ist der ggT. Weil sich die Zahlen alle zwei Schritte mindestens halbieren, ist das Verfahren auch bei sehr großen Zahlen schnell. Für drei oder vier Zahlen bestimmt der Rechner zuerst den ggT der ersten beiden und dann den ggT dieses Ergebnisses mit der nächsten Zahl. Alle Divisionen stehen in der zweiten Tabelle.
Am häufigsten braucht man den ggT zum Kürzen von Brüchen: 36/60 wird durch den ggT 12 zu 3/5, das erledigt auch der Bruchrechner. Auf dieselbe Weise vereinfachen Sie Verhältnisse wie 36 : 60 zu 3 : 5, mit Proportionen rechnet der Dreisatz-Rechner. Das Gegenstück zum ggT ist das kleinste gemeinsame Vielfache. Bei zwei Zahlen gilt ggT · kgV = a · b, das kgV berechnet der kgV-Rechner. Die Fläche, die gleich große Fliesen bedecken, ermittelt der Quadratmeterrechner.
Zur Formel
Mit Primfaktoren: 12 = 2² · 3 und 18 = 2 · 3² haben die Primfaktoren 2 und 3 gemeinsam, der kleinste Exponent ist jeweils 1, also ist der ggT 2 · 3 = 6. Ein Primfaktor, der in einer der Zahlen fehlt, geht nicht in das Produkt ein. Haben die Zahlen keinen Primfaktor gemeinsam, ist der ggT gleich 1.
Der euklidische Algorithmus beruht darauf, dass ggT(a, b) = ggT(b, r) gilt, wobei r der Rest der Division von a durch b ist. Jede Division ersetzt das Zahlenpaar durch ein kleineres mit demselben ggT, bis der Rest 0 wird. Für 18 und 12 gilt 18 = 1 · 12 + 6 und dann 12 = 2 · 6 + 0, der letzte Divisor ist also 6.
Bei zwei Zahlen hängen ggT und kgV eng zusammen: ggT(a, b) · kgV(a, b) = a · b. Für 12 und 18 ist 6 · 36 = 216 = 12 · 18. Daraus folgt kgV(a, b) = a · b / ggT(a, b).
Rechenbeispiel
Was ist der ggT von 143 und 65?
- Primfaktorzerlegung: 143 = 11 · 13 und 65 = 5 · 13.
- Gemeinsam ist nur der Primfaktor 13, der ggT ist also 13.
- Mit dem euklidischen Algorithmus: 143 = 2 · 65 + 13, dann 65 = 5 · 13 + 0. Der letzte Divisor ist 13, dasselbe Ergebnis.
Der ggT von 143 und 65 ist 13. Das ist die größte Zahl, durch die sich beide Zahlen ohne Rest teilen lassen.
Beispiel in den Rechner übernehmenHäufige Fragen
Was ist der ggT von 75 und 100?
Der ggT von 75 und 100 ist 25. Mit Primfaktoren: 75 = 3 · 5² und 100 = 2² · 5², gemeinsam ist 5² = 25. Mit dem euklidischen Algorithmus: 100 = 1 · 75 + 25, dann 75 = 3 · 25 + 0, der letzte Divisor ist 25. Tragen Sie 75 und 100 ein, um diesen Weg im Rechner zu sehen.
Was ist der ggT von 6 und 9?
Der ggT von 6 und 9 ist 3. Die Teiler von 6 sind 1, 2, 3 und 6, die von 9 sind 1, 3 und 9. Gemeinsam sind 1 und 3, und die größere davon ist 3. Der euklidische Algorithmus bestätigt es: 9 = 1 · 6 + 3 und 6 = 2 · 3 + 0.
Was bedeutet ggT in der Mathematik?
ggT steht für größter gemeinsamer Teiler: die größte natürliche Zahl, durch die sich zwei oder mehr ganze Zahlen ohne Rest teilen lassen. Der ggT von 12 und 18 ist 6. Englisch heißt er gcd, greatest common divisor. Ist der ggT gleich 1, nennt man die Zahlen teilerfremd.
Wie berechnet man den ggT mit der Primfaktorzerlegung?
Zerlegen Sie jede Zahl in Primfaktoren, nehmen Sie die Primfaktoren, die in allen Zahlen vorkommen, jeweils mit dem kleinsten Exponenten, und multiplizieren Sie sie. Für 2.970 = 2 · 3³ · 5 · 11 und 12.936 = 2³ · 3 · 7² · 11 ergibt das 2 · 3 · 11 = 66. Der Rechner zeigt die Zerlegung jeder Zahl in einer Tabelle.
Wie funktioniert der euklidische Algorithmus?
Teilen Sie die größere Zahl durch die kleinere und merken Sie sich den Rest. Dann teilen Sie den Divisor durch diesen Rest und wiederholen das, bis der Rest 0 ist. Der letzte Divisor ist der ggT. Für 1.071 und 462 gilt 1.071 = 2 · 462 + 147, 462 = 3 · 147 + 21 und 147 = 7 · 21 + 0, der ggT ist also 21.
Wie berechne ich das kgV, wenn ich den ggT kenne?
Bei zwei Zahlen gilt kgV(a, b) = a · b / ggT(a, b). Für 75 und 100 ist der ggT 25, also ist das kgV 75 · 100 / 25 = 300. Bei mehr als zwei Zahlen rechnen Sie das kgV schrittweise oder über die Primfaktoren. Der kgV-Rechner übernimmt das und nennt auch den ggT.
Wie berechnet man den ggT von drei oder mehr Zahlen?
Wenden Sie den euklidischen Algorithmus schrittweise an: ggT(a, b, c) = ggT(ggT(a, b), c). Für 12, 18 und 30 ist ggT(12, 18) = 6 und ggT(6, 30) = 6. Mit Primfaktoren zählen nur die Faktoren, die in allen Zahlen vorkommen. Der Rechner nimmt zwei bis vier Zahlen und listet alle Divisionen auf.
Wann sind Zahlen teilerfremd?
Zahlen sind teilerfremd, wenn ihr ggT gleich 1 ist, sie also außer 1 keinen gemeinsamen Teiler haben. Es müssen keine Primzahlen sein: 8 und 15 sind teilerfremd. Bei drei Zahlen genügt es, dass alle zusammen den ggT 1 haben, auch wenn je zwei einen Teiler gemeinsam haben, wie bei 6, 10 und 15.
Wofür braucht man den ggT?
Am häufigsten zum Kürzen von Brüchen: Teilen Sie Zähler und Nenner durch ihren ggT, erhalten Sie den vollständig gekürzten Bruch, bei 36/60 durch 12 also 3/5. Auch Verhältnisse lassen sich so vereinfachen. Der ggT hilft außerdem bei gleich großen Stücken ohne Rest, etwa der größten quadratischen Fliese für einen Boden von 360 mal 240 cm: 120 cm.
Was ist der ggT, wenn eine Zahl die andere teilt?
Dann ist der ggT die kleinere Zahl. Der ggT von 3 und 6 ist 3, und der ggT von 7 und 7 ist 7. Der euklidische Algorithmus endet in diesem Fall schon nach einer Division, weil der Rest sofort 0 ist.
Gibt es einen Trick, um den ggT schnell zu finden?
Kürzen Sie zuerst gemeinsame Faktoren, die Sie sofort sehen, etwa gerade Zahlen durch 2 oder Zahlen auf 0 und 5 durch 5, und multiplizieren Sie diese am Ende. Prüfen Sie außerdem, ob die kleinere Zahl die größere teilt, dann sind Sie fertig. Sonst bleibt der euklidische Algorithmus der sicherste Weg, auch bei großen Zahlen.
Wie groß dürfen die Zahlen im Rechner sein?
Der Rechner nimmt positive ganze Zahlen bis 1.000.000.000.000. Bis dahin sind alle Rechenschritte exakt, auch die Primfaktorzerlegung. Negative Zahlen tragen Sie mit ihrem Betrag ein, denn der ggT ändert sich durch das Vorzeichen nicht: ggT(−a, b) = ggT(a, b).
- Euklid, Elemente, Buch VII, Satz 2 (das größte gemeinsame Maß zweier Zahlen), Ausgabe von D. Joyce (Clark University)
- Größter gemeinsamer Teiler (Wikipedia)
- Euklidischer Algorithmus (Wikipedia)