Wie es funktioniert
Das kleinste gemeinsame Vielfache (kgV) einer Zahlenmenge ist die kleinste positive Zahl, in der jede Zahl der Menge restlos aufgeht. Die häufigste Alltags-Anwendung ist die Bruchaddition: Für 1/4 + 1/6 sucht man das kgV von 4 und 6 (= 12), bringt beide Brüche auf Zwölftel und addiert. Der Rechner ermittelt das kgV über die ggT-Identität — kgV(a, b) = a × b / ggT(a, b) — mittels euklidischem Algorithmus. Für drei oder mehr Zahlen wird paarweise reduziert: kgV(a, b, c) = kgV(kgV(a, b), c).
Die Formel
a, b: positive ganze Zahlen (Vorzeichen werden entfernt; die Formel nutzt |a|, |b|). Die kgV-über-ggT-Identität ist für jedes Zahlenpaar exakt und vermeidet den naiven Ansatz „Vielfache aufzählen, bis ein Treffer kommt", der O(min(a, b)) wäre — bei großen Zahlen langsam. Die paarweise Reduktion erweitert das auf beliebig viele Eingaben in O(n) Aufrufen des ggT.
Beispielrechnung
- Zahlen: 4, 6, 8
- kgV(4, 6) = |4 × 6| / ggT(4, 6) = 24 / 2 = 12
- kgV(12, 8) = |12 × 8| / ggT(12, 8) = 96 / 4 = 24
- kgV(4, 6, 8) = 24. Probe: 24 / 4 = 6, 24 / 6 = 4, 24 / 8 = 3 — alles ganze Zahlen, also ist 24 durch alle drei teilbar. ✓
Häufig gestellte Fragen
Warum die ggT-Identität verwenden, statt Vielfache zu listen?
Vielfache aufzählen klappt bei kleinen Zahlen (kgV von 4 und 6: 4, 8, 12 — Treffer!), skaliert aber schlecht. kgV(99, 100) verlangt fast 100 Vielfache, bis die Antwort kommt; kgV(99.991, 100.000) bräuchte Millionen. Die ggT-Identität reduziert jedes Problem auf einen einzigen Aufruf des euklidischen Algorithmus, der unabhängig von der Größe in rund log₂(min(a, b)) Schritten konvergiert. Damit braucht kgV(99.991, 100.000) etwa 16 Schritte statt 99.991. Gleiches Ergebnis, drastisch schneller.
Wann braucht man das kgV im echten Leben?
Am häufigsten: beim Addieren oder Subtrahieren von Brüchen mit verschiedenen Nennern. Für 3/4 + 5/6 braucht man einen gemeinsamen Nenner — das kgV von 4 und 6 (12). Weitere Anwendungen: zeitlich wiederkehrende Ereignisse synchronisieren („Bus A alle 8 Minuten, Bus B alle 12 — wann fahren sie zusammen?" → kgV = 24 min), Übersetzungen bei Zahnrädern, Musiktheorie (wann decken sich zwei Rhythmen?) und Olympiade-Aufgaben. Nach der Schulzeit ist die Bruchrechnung meist die einzige Stelle, an der man es noch braucht.
Was, wenn ich 0 oder eine negative Zahl mit eingebe?
Vorzeichen werden entfernt — der Algorithmus arbeitet mit Beträgen, also kgV(−4, 6) = kgV(4, 6) = 12. Das ist die mathematische Standardkonvention; manche Lehrbücher definieren das kgV nur für positive ganze Zahlen, aber das Streichen der Vorzeichen ist eine harmlose und praktische Verallgemeinerung. Mit 0 ist kgV(0, was auch immer) = 0, mathematisch korrekt, aber selten nützlich — bei 0-Ausgabe Eingabe prüfen.
Gibt es eine geschlossene Form für das kgV von mehr als zwei Zahlen?
Nicht wie beim ggT. Für drei Zahlen lässt sich kgV(a, b, c) = a × b × c / ggT(ggT(a, b) × ggT(b, c) × ggT(a, c), …) hinschreiben, das wird aber schnell unleserlich und ist nicht schneller als die paarweise Reduktion: kgV(a, b, c) = kgV(kgV(a, b), c). Die paarweise Variante nutzt jede Standardbibliothek und jedes Lehrbuch, auch dieser Rechner. Die Beziehung a × b × c × … = ggT(…) × kgV(…) verallgemeinert sich nur sauber auf zwei Zahlen; bei mehr gilt ggT × kgV ≠ Produkt nicht mehr.