ggT und kgV

Berechnung von ggT und kgV

Der größte gemeinsame Teiler (ggT) einer Zahlenmenge ist die größte Zahl, die restlos in alle teilt, und das kleinste gemeinsame Vielfache (kgV) ist die kleinste Zahl, in die alle restlos teilen. Geben Sie zwei oder mehr ganze Zahlen ein, und dieser Rechner findet beide sofort.

Die Methode

Der ggT wird mit dem euklidischen Algorithmus gefunden — einer Methode, die über 2.000 Jahre zurückreicht: Teilen Sie wiederholt die größere Zahl durch die kleinere und ersetzen Sie die größere durch den Rest, bis der Rest null erreicht. Der letzte von null verschiedene Wert ist der ggT.

Sobald der ggT bekannt ist, ergibt sich das kgV zweier Zahlen direkt daraus:

$$\text{kgV}(\vA{a}, \vB{b}) = \frac{\vA{a} \times \vB{b}}{\vC{\text{ggT}(\vA{a}, \vB{b})}}$$

Bei mehr als zwei Zahlen wendet dieser Rechner beide Methoden paarweise über die gesamte Liste an.

Beispielrechnung

Ermittlung des ggT und kgV von 12 und 18:

1. Euklidischer Algorithmus: 18 ÷ 12 lässt einen Rest von 6; 12 ÷ 6 lässt einen Rest von 0. Der ggT ist $\vC{6}$.
2. $\text{kgV}(\vA{12}, \vB{18}) = (12 \times 18) \div \vC{6} = 216 \div \vC{6} = 36$.

Wichtige Einflussfaktoren

• Zwei Zahlen mit einem GGT von 1 heißen „teilerfremd” oder „relativ prim”, eine wirklich nützliche Klassifikation. Wenn der GGT 1 ist, teilen sich die beiden Zahlen keine gemeinsamen Faktoren außer 1 — dies ist in Bereichen wie Kryptografie und Zahlentheorie relevant, und es bedeutet auch, dass ihr KGV einfach ihr Produkt ist.
• Der euklidische Algorithmus ist bei großen Zahlen dramatisch schneller, als jeden Faktor aufzulisten. Den GGT durch Auflisten aller Faktoren jeder Zahl und deren Vergleich zu finden wird bei großen Zahlen unpraktikabel — der euklidische Algorithmus findet die Antwort in nur einer Handvoll Schritte, unabhängig davon, wie groß die Zahlen sind, genau deshalb ist er seit über 2.000 Jahren die Standardmethode.
• GGT und KGV verallgemeinern sich sauber auf mehr als zwei Zahlen, mit demselben paarweisen Baustein. Das Anwenden der Zwei-Zahlen-Formel über eine Liste hinweg — GGT(GGT(a,b), c), und entsprechend für KGV — erweitert beide Konzepte korrekt auf beliebig viele Eingaben, genau so behandelt dieser Rechner eine Liste mit mehr als zwei Zahlen.
• Diese Konzepte tauchen ständig außerhalb der reinen Mathematik auf, bei Terminplanungs- und Aufteilungsproblemen. Über das Kürzen von Brüchen hinaus beantwortet das KGV „wann treffen sich zwei wiederkehrende Ereignisse als nächstes” (wie Busfahrpläne oder blinkende Lichter), und der GGT beantwortet „wie groß ist die größte gleich große Gruppe, in die ich das aufteilen kann” (wie das Aufteilen von Gegenständen in identische Bündel ohne Rest).

Häufige Fehler

• Verwechseln, welcher ggT und welcher kgV ist. Die Namen klingen ähnlich und werden leicht vertauscht — der ggT ist immer das kleinere der beiden Ergebnisse (ein gemeinsamer Teiler, kann also nicht größer sein als die kleinste Eingabezahl), während das kgV immer das größere ist (ein gemeinsames Vielfaches, also mindestens so groß wie die größte Eingabezahl).
• Annahme, dass der ggT eine der verglichenen Zahlen sein muss. Wie oben behandelt, ist der ggT die größte Zahl, die restlos in jede Eingabe teilt — bei 12 und 18 ist das 6, nicht 12 oder 18 selbst, obwohl beide auch restlos in mindestens eine der Eingaben teilen.
• Manuelles Auflisten jedes Faktors bei großen Zahlen statt der Verwendung des euklidischen Algorithmus. Wie oben behandelt, wird dies mit wachsenden Zahlen langsam und fehleranfällig — der euklidische Algorithmus, den dieser Rechner verwendet, findet dieselbe Antwort in nur einer Handvoll Schritten unabhängig von der Größe.
• Multiplizieren der beiden Zahlen, um das kgV zu erhalten, ohne vorher durch den ggT zu teilen. Wie oben behandelt, liefert eine einfache Multiplikation nur dann das korrekte kgV, wenn die beiden Zahlen teilerfremd sind (ggT von 1) — bei Zahlen, die einen gemeinsamen Faktor teilen, ergibt das Auslassen der Division durch den ggT ein Vielfaches des wahren kgV, nicht das kgV selbst.

Wissenswertes

• Einen Bruch auf seine einfachste Form zu kürzen ist genau eine ggT-Berechnung — der Bruchrechner vereinfacht Brüche mit demselben ggT, den dieser Rechner direkt berechnet.
• Einen gemeinsamen Nenner zum Addieren oder Subtrahieren von Brüchen zu finden ist genau eine kgV-Berechnung — dieselbe Beziehung in die andere Richtung.
• Der Primfaktorzerlegungsrechner und der Verhältnisrechner stützen sich beide auf dieselbe Idee des gemeinsamen Faktors, nur aus einem anderen Blickwinkel — der eine zerlegt eine Zahl in ihre Primzahl-Bausteine, der andere reduziert ein Verhältnis auf seine einfachste ganzzahlige Form.