GGT-Rechner - Größter gemeinsamer Teiler von Zahlen
Berechne den größten gemeinsamen Teiler (GGT, GCF oder GCD) von zwei oder mehr ganzen Zahlen mit dem euklidischen Algorithmus oder der Primfaktorzerlegung.
Gib zwei oder mehr positive ganze Zahlen ein, um ihren größten gemeinsamen Teiler zu finden. Wähle deinen bevorzugten Algorithmus, um auch die schrittweise Herleitung zu sehen.
GGT-Rechner - Größter gemeinsamer Teiler von Zahlen
Berechne den größten gemeinsamen Teiler (GGT, GCF oder GCD) von zwei oder mehr ganzen Zahlen mit dem euklidischen Algorithmus oder der Primfaktorzerlegung.
Gib zwei oder mehr positive ganze Zahlen ein, getrennt durch Kommas oder Leerzeichen, z. B. 24 36 48
Über den größten gemeinsamen Teiler
Der größte gemeinsame Teiler (GGT), auch als Greatest Common Factor (GCF), Greatest Common Divisor (GCD) oder Highest Common Factor (HCF) bekannt, ist die größte positive ganze Zahl, die jede Zahl einer gegebenen Menge ganzer Zahlen ohne Rest teilt. Zum Beispiel ist der GGT von 12 und 18 gleich 6, weil 6 die größte Zahl ist, die sowohl 12 als auch 18 exakt teilt.
Die zwei gebräuchlichsten Algorithmen zur Berechnung des GGT sind der euklidische Algorithmus und die Primfaktorzerlegung. Für große Zahlen ist der euklidische Algorithmus effizienter. Er funktioniert, indem das Paar (a, b) wiederholt durch (b, a mod b) ersetzt wird, bis der Rest 0 ist; der letzte von null verschiedene Wert von b ist der GGT. Der Algorithmus läuft in O(log min(a,b)) Schritten und ist daher selbst bei sehr großen ganzen Zahlen extrem schnell.
Die Primfaktorzerlegung berechnet den GGT, indem jede Zahl als Produkt von Primzahlpotenzen dargestellt wird. Anschließend wird das Produkt aller Primzahlen gebildet, jeweils hoch der kleinsten Potenz, die über alle Zahlen hinweg vorkommt. Zum Beispiel gilt 12 = 2^2 * 3 und 18 = 2 * 3^2, also GGT(12, 18) = 2^1 * 3^1 = 6. Obwohl sie bei großen Zahlen weniger effizient als der euklidische Algorithmus ist, bietet die Primfaktorzerlegung einen klaren didaktischen Einblick, warum der GGT genau diesen Wert hat.
Der GGT hat viele praktische Anwendungen. In der Arithmetik wird er verwendet, um Brüche auf ihre einfachste Form zu kürzen: Um a/b zu vereinfachen, teilt man sowohl Zähler als auch Nenner durch GGT(a, b). In der Geometrie gibt der GGT zweier Längen das längste Lineal an, das beide ohne Rest misst. In der Informatik tritt der GGT in modularer Arithmetik, kryptografischen Algorithmen (z. B. bei der RSA-Schlüsselerzeugung) und Datenkompression auf.
Für mehr als zwei Zahlen wird der GGT iterativ berechnet. GGT(a, b, c) = GGT(GGT(a, b), c). Dieser Rechner verarbeitet beliebig viele positive ganze Zahlen und unterstützt sowohl den euklidischen Algorithmus (für schnelle Ergebnisse) als auch die Primfaktorzerlegung (für eine detaillierte Schritt-für-Schritt-Ausgabe). Die Primfaktorzerlegungsansicht ist besonders hilfreich für Lernende, die Faktoren und Teilbarkeit verstehen möchten.
Beispiele
Beispielhafte GGT-Berechnungen mit Erklärungen:
| Zahlen | GGT | Hinweise |
|---|---|---|
| 12, 18 | 6 | 12 = 2^2 * 3; 18 = 2 * 3^2; GGT = 6 |
| 24, 36, 48 | 12 | Alle sind durch 12 teilbar |
| 17, 31 | 1 | Beide sind Primzahlen, daher GGT = 1 (teilerfremd) |
| 100, 75, 50 | 25 | Alle sind durch 25 teilbar |
Anleitung
- Gib im Feld Zahlen zwei oder mehr positive ganze Zahlen ein, getrennt durch Kommas oder Leerzeichen.
- Wähle deinen bevorzugten Algorithmus: euklidischer Algorithmus für schnelle Berechnung oder Primfaktorzerlegung für die schrittweise Herleitung.
- Klicke auf Berechnen, um den GGT sofort zu ermitteln.
- Wenn du Primfaktorzerlegung gewählt hast, sieh dir im Abschnitt Schritte an, wie jede Zahl zerlegt wird.
- Klicke auf Zurücksetzen, um die Eingabe zu löschen und eine neue Berechnung zu starten.
Häufig gestellte Fragen
Was ist der Unterschied zwischen GCF, GCD, GGT und HCF?
GCF (Greatest Common Factor), GCD (Greatest Common Divisor), GGT (größter gemeinsamer Teiler) und HCF (Highest Common Factor) bezeichnen dasselbe Konzept: die größte positive ganze Zahl, die jede Zahl einer Menge ohne Rest teilt. Die Begriffe unterscheiden sich je nach Region und Kontext, die mathematische Definition ist jedoch identisch.
Wie funktioniert der euklidische Algorithmus?
Der euklidische Algorithmus berechnet GGT(a, b), indem das Paar wiederholt durch (b, a mod b) ersetzt wird, bis der Rest null ist. Der letzte von null verschiedene Rest ist der GGT. Beispiel GGT(48, 18): 48 mod 18 = 12, dann 18 mod 12 = 6, dann 12 mod 6 = 0, also GGT = 6.
Wie funktioniert die Primfaktorzerlegung?
Jede Zahl wird als Produkt von Primzahlpotenzen dargestellt. Der GGT ist das Produkt jeder Primzahl, erhöht auf den kleinsten Exponenten, mit dem sie in allen Zahlen vorkommt. Für 12 = 2^2 * 3 und 18 = 2 * 3^2 sind die kleinsten Exponenten 2^1 und 3^1, also GGT = 6.
Was bedeutet ein GGT von 1?
Ein GGT von 1 bedeutet, dass die Zahlen teilerfremd (relativ prim) sind: Sie haben außer 1 keine gemeinsamen Teiler. Teilerfremde Zahlen treten in gekürzten Brüchen (Zähler und Nenner teilerfremd), in der RSA-Kryptografie (Bestandteile öffentlicher Schlüssel) und in vielen zahlentheoretischen Beweisen auf.
Kann ich den GGT von mehr als zwei Zahlen finden?
Ja. Für eine Liste von Zahlen wird der GGT iterativ berechnet: GGT(a, b, c) = GGT(GGT(a, b), c) und so weiter. Dieser Rechner wendet diesen iterativen Ansatz automatisch auf beliebig viele Eingaben an.
Wie wird der GGT zum Kürzen von Brüchen verwendet?
Um einen Bruch a/b auf die kleinste Form zu kürzen, teilt man Zähler und Nenner durch GGT(a, b). Beispiel 18/24 vereinfacht: GGT(18, 24) = 6, also 18/24 = 3/4. Ein Bruch ist vollständig gekürzt, wenn sein GGT gleich 1 ist.