Berechne den größten gemeinsamen Teiler (ggT) und das kleinste gemeinsame Vielfache (kgV) zweier ganzer Zahlen.
Der größte gemeinsame Teiler ist die größte Zahl, die beide Ausgangszahlen ohne Rest teilt. Der Rechner ermittelt ihn mit dem euklidischen Algorithmus: Er teilt wiederholt die größere durch die kleinere Zahl und rechnet mit dem Rest weiter, bis dieser null wird.
Das kleinste gemeinsame Vielfache ist die kleinste Zahl, die ein Vielfaches beider Ausgangszahlen ist. Es ergibt sich aus dem Produkt der beiden Zahlen geteilt durch ihren größten gemeinsamen Teiler.
Beispiel: Für 12 und 18 ist der größte gemeinsame Teiler 6 und das kleinste gemeinsame Vielfache 36. Sind zwei Zahlen teilerfremd – haben sie also nur die 1 als gemeinsamen Teiler – ist ihr kleinstes gemeinsames Vielfaches gleich ihrem Produkt.
Der ggT wird zum Kürzen von Brüchen gebraucht, das kgV zum Finden des Hauptnenners beim Addieren von Brüchen. Die Berechnung läuft vollständig in deinem Browser.
Der größte gemeinsame Teiler lässt sich ohne Primfaktorzerlegung finden – mit einem Verfahren, das seit über zweitausend Jahren unverändert funktioniert. Man teilt die größere durch die kleinere Zahl und rechnet mit dem Rest weiter, bis dieser null wird; die letzte Zahl ungleich null ist der ggT. Für 48 und 18 heißt das: 48 geteilt durch 18 lässt Rest 12, 18 durch 12 lässt Rest 6, 12 durch 6 lässt Rest 0 – der ggT ist 6. Das Verfahren braucht selbst bei sehr großen Zahlen nur wenige Schritte und ist deshalb bis heute Grundlage kryptografischer Berechnungen.
Beide Größen hängen fest zusammen: ggT(a,b) · kgV(a,b) = a · b. Ist der größte gemeinsame Teiler bekannt, folgt das kleinste gemeinsame Vielfache also durch eine einzige Division. Für 48 und 18 ergibt sich 48 × 18 ÷ 6 = 144. Diese Beziehung gilt allerdings nur für zwei Zahlen; bei drei und mehr muss schrittweise vorgegangen werden.
Der ggT kürzt Brüche vollständig in einem Schritt: 48/18 wird durch Division beider Teile durch 6 zu 8/3. Das kgV wird gebraucht, um Brüche auf einen gemeinsamen Nenner zu bringen, und beantwortet außerdem alle Fragen nach wiederkehrenden Ereignissen – wenn ein Bus alle 12 und ein anderer alle 18 Minuten fährt, treffen sie sich alle 36 Minuten. In der Technik taucht dasselbe Prinzip bei Zahnrädern und Übersetzungen auf.
Zwei Zahlen ohne gemeinsamen Teiler außer 1 heißen teilerfremd; ihr ggT ist 1 und ihr kgV schlicht das Produkt beider Zahlen.
Zum Kürzen und Erweitern von Brüchen ist der Bruchrechner die passende Ergänzung, für quadratische Gleichungen mit ganzzahligen Lösungen der pq-Formel-Rechner.