GGT und KGV – Grundlagen und Anwendungen
Teiler, Vielfache und der euklidische Algorithmus
Der größte gemeinsame Teiler (GGT) und das kleinste gemeinsame Vielfache (KGV) gehören zu den wichtigsten Begriffen der elementaren Zahlentheorie. Sie spielen in der Schulmathematik, aber auch in der angewandten Mathematik und Informatik eine zentrale Rolle. Der GGT zweier Zahlen a und b ist die größte Zahl, die beide ohne Rest teilt. Das KGV ist die kleinste Zahl, die von beiden ohne Rest geteilt wird.
Unser Rechner verwendet den euklidischen Algorithmus, einen der ältesten Algorithmen der Mathematik (ca. 300 v. Chr.). Er berechnet den GGT iterativ durch wiederholte Division mit Rest: GGT(12, 18): 18 mod 12 = 6, dann 12 mod 6 = 0 → GGT = 6. Das KGV folgt dann direkt aus der Formel KGV = (a × b) / GGT. Für 12 und 18: KGV = (12 × 18) / 6 = 36.
Die wichtigste Alltagsanwendung des GGT ist das Kürzen von Brüchen. Um den Bruch 18/24 zu kürzen: GGT(18, 24) = 6, also 18/24 = 3/4. Das KGV wird bei der Addition von Brüchen mit ungleichen Nennern benötigt: 1/4 + 1/6 erfordert den gemeinsamen Nenner kgV(4, 6) = 12. Damit gilt: 3/12 + 2/12 = 5/12. Ohne KGV müsste man mit dem Produkt 4 × 6 = 24 arbeiten und kürzen.
In der Informatik und Kryptographie ist der GGT fundamental: Der RSA-Verschlüsselungsalgorithmus basiert auf der Schwierigkeit, den GGT großer Zahlen zu berechnen. Die Taktfrequenz-Synchronisationin der Signalverarbeitung nutzt das KGV zweier Frequenzen. Selbst in der Musiktheorie entspricht der Rhythmus dem KGV der Taktlängen. Der GGT-Rechner ist damit nicht nur für Schüler nützlich, sondern auch für Ingenieure und Informatiker.