GGT-Rechner - Größter gemeinsamer Teiler

Der größte gemeinsame Teiler (GCF), auch größter gemeinsamer Teiler (GCD) oder höchster gemeinsamer Faktor (HCF) genannt, ist die größte positive ganze Zahl, die jede Zahl einer gegebenen Menge ohne Rest teilt. Zum Beispiel ist der GCF von 12 und 18 gleich 6, weil 6 die größte Zahl ist, die sowohl 12 als auch 18 genau teilt. Die zwei häufigsten Algorithmen zur Berechnung des GCF sind der euklidische Algorithmus und die Primfaktorzerlegung. Für große Zahlen ist der euklidische Algorithmus der effizientere von beiden. Er ersetzt wiederholt das Zahlenpaar (a, b) durch (b, a mod b), bis der Rest 0 ist; der letzte von 0 verschiedene Wert von b ist der GCF. Der Algorithmus benötigt O(log min(a,b)) Schritte und ist daher selbst für sehr große ganze Zahlen extrem schnell. Die Primfaktorzerlegung berechnet den GCF, indem jede Zahl als Produkt von Primzahlen mit Potenzen dargestellt wird und dann das Produkt jeder Primzahl mit dem kleinsten vorkommenden Exponenten über alle Zahlen hinweg gebildet wird. Zum Beispiel gilt 12 = 2^2 * 3 und 18 = 2 * 3^2, also ist GCF(12, 18) = 2^1 * 3^1 = 6. Obwohl diese Methode für große Zahlen weniger effizient ist als der euklidische Algorithmus, liefert sie einen klaren didaktischen Einblick, warum der GCF genau diesen Wert hat. Der GCF hat viele praktische Anwendungen. In der Arithmetik wird er verwendet, um Brüche zu kürzen: Um a/b zu vereinfachen, teilt man Zähler und Nenner durch GCF(a, b). In der Geometrie gibt der GCF zweier Längen das längste Lineal an, mit dem beide ohne Rest gemessen werden können. In der Informatik taucht der GCF in der modularen Arithmetik, in kryptografischen Algorithmen (etwa bei der RSA-Schlüsselerzeugung) und bei der Datenkompression auf. Für mehr als zwei Zahlen wird der GCF iterativ berechnet. GCF(a, b, c) = GCF(GCF(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 Primfaktoransicht ist besonders nützlich für Lernende, die Faktoren und Teilbarkeit verstehen möchten.