ggT-Rechner

Der größte gemeinsame Teiler zweier ganzer Zahlen ist die größte ganze Zahl, die beide exakt teilt, und er begegnet Ihnen ständig: beim Kürzen von Brüchen, beim Aufteilen von Mengen in gleiche Gruppen, beim Bemessen von Fliesen für einen Boden oder beim Vereinfachen von Verhältnissen im Code. Diese Fähigkeit berechnet ihn mit dem euklidischen Algorithmus, derselben Methode, die Mathematiker seit über zweitausend Jahren nutzen, und gibt eine einzige ganze Zahl zurück. Senden Sie zwei ganze Zahlen — positiv, negativ oder null, als Zahlen oder als exakte numerische Zeichenketten — und erhalten Sie ihren größten gemeinsamen Teiler.

Was der größte gemeinsame Teiler wirklich ist

Nehmen Sie zwei ganze Zahlen, etwa 48 und 18. Die Zahlen, die 48 exakt teilen, sind 1, 2, 3, 4, 6, 8, 12, 16, 24 und 48; die Teiler von 18 sind 1, 2, 3, 6, 9 und 18. Die Teiler, die beide gemeinsam haben, sind 1, 2, 3 und 6, und der größte davon — 6 — ist der größte gemeinsame Teiler, geschrieben ggt(48, 18) = 6.

Das Auflisten der Teiler funktioniert bei kleinen Zahlen, skaliert aber miserabel: Eine fünfzehnstellige Zahl zu faktorisieren ist wirklich schwer. Der ggT-Rechner vermeidet das Faktorisieren vollständig. Er nutzt den euklidischen Algorithmus, der auf einer Beobachtung beruht: Jeder gemeinsame Teiler von a und b teilt auch den Rest, der entsteht, wenn man die größere durch die kleinere Zahl teilt.

Ersetzt man die größere Zahl durch diesen Rest, schrumpft das Problem bei jedem Schritt, während alle gemeinsamen Teiler erhalten bleiben, bis eine der Zahlen null erreicht und die andere die Antwort ist. Die gesamte Berechnung braucht selbst für die größten ganzen Zahlen, die JavaScript exakt darstellen kann, höchstens ein paar Dutzend Schritte, und das Ergebnis ist immer exakt — keine Gleitkommazahlen, keine Näherung.

Eingaben, Vorzeichen, Null und Fehler

Der Endpunkt nimmt zwei Pflichtfelder entgegen, a und b. Vorzeichen spielen keine Rolle: ggt(-48, 18) ist gleich ggt(48, 18), denn ein Teiler einer Zahl teilt auch ihr Gegenteil, also arbeitet der Algorithmus mit den Beträgen. Null ist eine legitime Eingabe mit präziser Bedeutung — ggt(17, 0) ist 17, da jede ganze Zahl null teilt und der größte Teiler von 17 die 17 selbst ist —, aber zwei Nullen werden abgelehnt, weil jede ganze Zahl null teilt und es keinen größten gibt.

Die Beträge sind auf 9007199254740991 begrenzt, die größte ganze Zahl, die JavaScript exakt darstellt; alles Größere ließe sich nicht exakt verarbeiten und wird abgelehnt.

Wo sie passt und was sie kostet

Der größte gemeinsame Teiler begegnet Ihnen öfter, als der Name vermuten lässt. Einen Bruch vollständig zu kürzen bedeutet, Zähler und Nenner durch ihren ggT zu teilen. Eine Lieferung ohne Rest in identische Kartons aufzuteilen, die größte quadratische Fliese zu wählen, die einen rechteckigen Boden ohne Zuschnitt bedeckt, und ein Seitenverhältnis in einem responsiven Layout zu vereinfachen, sind dieselbe Frage in verschiedener Kleidung.

Im Code taucht er in Schedulern, Hash-Funktionen und kryptografischen Routinen auf. Diese Fähigkeit ist bewusst minimal: Sie gibt den Teiler selbst zurück, sonst nichts, und lässt sich daher sauber mit allem kombinieren, das ihn verbraucht. Wenn Sie die vollständigen Divisionsschritte des euklidischen Algorithmus, die Bézout-Koeffizienten oder auch das kleinste gemeinsame Vielfache benötigen, decken Schwester-Fähigkeiten das ab.

Sie läuft auf unserem globalen Edge, ohne dass nach der Antwort etwas gespeichert wird, und dasselbe Modul betreibt den kostenlosen Rechner auf dieser Seite — Sie können jedes Ergebnis also von Hand nachprüfen, bevor Sie es in eine Pipeline einbinden.