Berechne den größten gemeinsamen Teiler (ggT) und das kleinste gemeinsame Vielfache (kgV) mit vollständigen Schritten.
Der größte gemeinsame Teiler (ggT) und das kleinste gemeinsame Vielfache (kgV) sind zwei der wichtigsten Konzepte der elementaren Zahlentheorie, mit Anwendungen vom Kürzen von Brüchen in der Mittelstufe bis zu kryptografischen Algorithmen, die das Internet sichern.
Der euklidische Algorithmus, beschrieben von Euklid um 300 v. Chr., ist einer der ältesten und effizientesten Algorithmen der Mathematik. Er berechnet den ggT in O(log(min(a,b))) Schritten und terminiert selbst für sehr große Zahlen schnell. Der Algorithmus wendet die Identität ggT(a, b) = ggT(b, a mod b) wiederholt an, bis der Rest Null ist.
Dieser Rechner zeigt den vollständigen euklidischen Algorithmus Schritt für Schritt für zwei Zahlen und berechnet auch ggT und kgV für Listen mehrerer Zahlen mittels der Verallgemeinerung: ggT(a, b, c) = ggT(ggT(a, b), c).
Finde ggT(48, 18): 48 = 2×18 + 12 → 18 = 1×12 + 6 → 12 = 2×6 + 0. ggT = 6. kgV = |48×18|/6 = 864/6 = 144. Prüfung: 144/48 = 3 ✓, 144/18 = 8 ✓.
Wende den euklidischen Algorithmus an, um ggT(48, 18) zu finden
Divisionsschritte (euklidischer Algorithmus)
48 = 2 × 18 + 12 → 18 = 1 × 12 + 6 → 12 = 2 × 6 + 0
ggT(48, 18) = letzter Rest ungleich Null
LCM = |a × b| / GCD
kgV(48, 18)
• ggT(a, b) × kgV(a, b) = |a × b|
• GCD(a, 0) = a (jede Zahl ist durch sich selbst teilbar)
• Wenn ggT(a, b) = 1, dann sind a und b teilerfremd
• Der euklidische Algorithmus läuft in O(log(min(a,b))) Zeit
• kgV wird zum Addieren von Brüchen mit unterschiedlichen Nennern verwendet