GCD / LCM Calculator

Den ggT- und kgV-Rechner verwenden

1. Die Felder Erste Zahl und Zweite Zahl mit den ganzen Zahlen füllen, von denen du ggT und kgV möchtest. Negative Vorzeichen und null sind beide erlaubt; das Werkzeug normalisiert auf absolute Werte vor dem Berechnen.
2. Berechnen drücken oder Enter drücken. ggT und kgV erscheinen nebeneinander, zusammen mit der Identität |a × b| = ggT(a, b) × kgV(a, b), mit deinen Zahlen ausgefüllt, damit du die Beziehung sehen kannst.
3. Das Schritt-Protokoll lesen unterhalb des Ergebnisses. Jede Division in Euklids Algorithmus wird als a = bq + r gezeigt, was den Prozess für Hausaufgaben oder Unterricht inspizierbar macht.
4. Erneut ausführen mit verschiedenen Eingaben so oft du möchtest; nichts wird zwischen Berechnungen gespeichert.
5. Jede Zeile des Schritt-Protokolls kopieren mit einem Klick, praktisch beim Einfügen der Ableitung in ein LaTeX-Dokument oder eine Chat-Nachricht.

Der Euklidische Algorithmus in Code

Die ggT-Routine implementiert Euklids Algorithmus mit der Rest-Variante: Während der zweite Operand nicht null ist, ersetze (a, b) durch (b, a mod b); der finale Wert von a ist der ggT. JavaScripts %-Operator gibt einen Wert mit dem Vorzeichen des Dividenden zurück, also hält die Absolutwert-Normalisierung am Anfang der Funktion die Schleifeninvariante sauber. Das kgV wird dann als |a * b| / ggT berechnet, wobei die Division vor der Multiplikation durchgeführt wird, wo möglich, um Zwischenüberlauf zu vermeiden, d.h. (a / ggT) * b.

Beide Routinen laufen im Browser ohne Netzwerkaufruf. Das Schritt-Protokoll wird während der Iteration erstellt, indem jedes { a, b, q, r }-Tupel in ein Array geschoben wird, das dann als Liste gerendert wird. Die Gesamtkosten sind O(log min(a, b)) Divisionen, der schlimmste Fall ist ein Paar aufeinanderfolgender Fibonacci-Zahlen - ein Ergebnis, das Gabriel Lamé 1844 bewies und das als erste Komplexitätsanalyse in der Geschichte des Gebietes gilt.

Wo ggT und kgV in echter Arbeit auftauchen

• Einen Bruch auf niedrigste Terme kürzen, indem Zähler und Nenner durch ihren ggT dividiert werden.
• Einen gemeinsamen Nenner für die Bruchaddition finden, was einfach das kgV der beiden Nenner ist.
• Die Periode zweier wiederkehrender Ereignisse berechnen - ein Bus alle 12 Minuten und ein anderer alle 18 Minuten treffen sich wieder nach kgV(12, 18) = 36 Minuten.
• Teilerfremdheit prüfen (ggT = 1) vor der Anwendung des Chinesischen Restsatzes oder der Wahl eines RSA-Exponenten.
• Ein Zahnrad-Verhältnis, ein Riemen-Verhältnis oder ein Musiktheorie-Intervall auf seine kanonische Form reduzieren.
• Herausfinden, wie viele Fliesen der Größe a mal b in ein größeres Rechteck passen, ohne zu schneiden - ein ggT-Problem.

Grenzfälle

• ggT(a, 0) = |a| für jede ganze Zahl a, weil jede ganze Zahl null teilt. Das Werkzeug gibt |a| sauber zurück statt in eine Endlosschleife zu geraten.
• ggT(0, 0) ist konventionell als 0 definiert, da keine positive ganze Zahl als "größte" bezeichnet werden kann. Das Werkzeug folgt dieser Konvention.
• kgV mit einem Null-Operanden ist 0, entsprechend der Konvention, dass jede nicht-nullige Zahl 0 teilt, also ist das "kleinste gemeinsame Vielfache", das ein Vielfaches von 0 ist, einfach 0.
• Negative Eingaben werden durch das Vorneweg-Nehmen absoluter Werte behandelt. ggT und kgV sind konventionell nicht-negativ in den ganzen Zahlen.
• Sehr große Eingaben bis zu Number.MAX_SAFE_INTEGER (2⁵³-1) funktionieren genau. Für größere Größenordnungen auf BigInt oder ein CAS umsteigen.
• Teilerfremde Paare ergeben ggT = 1 und kgV = |a * b|, was das maximale mögliche kgV für ein gegebenes Produkt ist; das ist ein kleiner aber nützlicher Plausibilitätscheck.

Hintergrund: Zweitausend Jahre desselben Algorithmus

Euklid formulierte den Algorithmus in Proposition VII.1 der Elemente (ca. 300 v. Chr.) unter Verwendung von Subtraktion statt der Modulus-Operation: Wiederholt ersetze das Größere von (a, b) durch die Differenz mit dem Kleineren, bis sie gleich sind. Die hier verwendete Modulus-basierte Variante ist für Operanden sehr unterschiedlicher Größe schneller, mathematisch aber identisch. Lamés Theorem von 1844 begrenzt die Anzahl der Iterationen auf das Fünffache der Anzahl der Dezimalstellen des kleineren Operanden, weshalb selbst zehnstellige Eingaben weniger als 50 Schritte benötigen. Der erweiterte Euklidische Algorithmus geht weiter und gibt auch ganze Zahlen x, y zurück, sodass a·x + b·y = ggT(a, b); diese Bezout-Koeffizientenform ermöglicht modulare Inverse und RSA-Schlüsselgenerierung. Dieses Werkzeug gibt nur ggT und kgV zurück, nicht die Bezout-Koeffizienten.

Alternativen und Kompromisse

Pythons math.gcd und math.lcm, JavaScripts eigene BigInt-basierte Lösungen und Befehlszeilenwerkzeuge wie bc oder factor berechnen ggT und kgV alle schneller für geskriptete Verwendung. Für gigantische Operanden mit Hunderten von Stellen ist das binäre ggT (Steins Algorithmus) kennenswert, weil er Divisionen zugunsten von Bit-Shifts und Subtraktionen vermeidet - historisch nützlich auf Hardware mit langsamer Division. Für symbolische oder Polynom-ggTs (nützlich in der Computeralgebra) brauchst du SymPy, Mathematica oder Maxima. Das Browser-Werkzeug gewinnt, wenn du zwei überschaubare Integer hast und die Antwort plus die Ableitung ohne Öffnen eines REPLs möchtest. Zeige-deine-Arbeit-Transkripte sind sein unterscheidendes Merkmal.