ggT- und kgV-Rechner

So funktioniert der ggT- und kgV-Rechner

Der ggT-kgV-Rechner nimmt zwei oder mehr Zahlen, durch Leerzeichen oder Komma getrennt, und zeigt den größten gemeinsamen Teiler und das kleinste gemeinsame Vielfache, dazu die Primfaktorzerlegung jeder Zahl, aus der man beides ablesen kann. Der ggT ist die größte Zahl, die alle eingegebenen Zahlen ohne Rest teilt, das kgV die kleinste Zahl, die von allen geteilt wird; der erste kürzt Brüche, das zweite bringt sie auf einen Nenner.

Merksatz: Der ggT nimmt von jedem Primfaktor die kleinste Hochzahl, das kgV die größte. Die Eselsbrücke für zwei Zahlen: ggT mal kgV gleich Produkt der beiden Zahlen, also kgV = a · b / ggT, und wer den ggT mit dem euklidischen Algorithmus hat, hat das kgV geschenkt.

Drei Beispiele:

• 24, 36 und 60: 24 = 2³ · 3, 36 = 2² · 3², 60 = 2² · 3 · 5. ggT = 2² · 3 = 12, kgV = 2³ · 3² · 5 = 360.
• 12 und 18: ggT 6, kgV 36, und die Probe 6 · 36 = 216 = 12 · 18 stimmt. Der Bruch 12/18 wird mit 6 gekürzt zu 2/3.
• Brüche addieren, 1/12 + 1/18: Hauptnenner kgV 36, also 3/36 + 2/36 = 5/36.

Formeln: ggT(a, b) · kgV(a, b) = a · b, euklidischer Algorithmus: ggT(a, b) = ggT(b, a mod b) bis der Rest 0 ist. Die Primfaktoren einzelner Zahlen und ihre Teiler liefert der Primzahl-Rechner, das Kürzen und Addieren von Brüchen der Bruchrechner.

Wissenswertes zum Thema

Drei Wege zum ggT

Der Schulweg ist die Primfaktorzerlegung: Jede Zahl so lange durch die kleinste Primzahl teilen, bis 1 bleibt, 24 = 2 · 2 · 2 · 3, 36 = 2 · 2 · 3 · 3, 60 = 2 · 2 · 3 · 5; für den ggT nimmt man jeden Primfaktor mit der kleinsten Hochzahl, die in allen Zahlen vorkommt, 2² · 3 = 12, für das kgV jeden mit der größten, 2³ · 3² · 5 = 360. Das funktioniert für beliebig viele Zahlen und zeigt, warum es klappt, wird aber bei großen Zahlen mühsam, 2.021 = 43 · 47 findet man nicht durch Probieren. Der zweite Weg ist der euklidische Algorithmus, der ganz ohne Zerlegung auskommt: Die größere Zahl durch die kleinere teilen, den Rest nehmen, die kleinere durch den Rest teilen, und so weiter, bis der Rest 0 ist; der letzte Teiler ist der ggT. 36 und 24: 36 = 1 · 24 + 12, 24 = 2 · 12 + 0, ggT 12. Dann 12 und 60: 60 = 5 · 12 + 0, ggT 12. Für mehrere Zahlen macht man es paarweise. Der dritte Weg ist die Teilerliste, alle Teiler beider Zahlen aufschreiben und den größten gemeinsamen suchen, für kleine Zahlen im Kopf: 12 hat 1, 2, 3, 4, 6, 12, 18 hat 1, 2, 3, 6, 9, 18, gemeinsam größter ist 6. Der Rechner nutzt die Zerlegung für die Anzeige und den Algorithmus für die Rechnung, auch bei großen Zahlen. Welche Zahlen überhaupt Primzahlen sind, zeigt der Primzahl-Rechner.

Wofür man ggT und kgV braucht

Brüche: Kürzen mit dem ggT von Zähler und Nenner, 12/18 wird 2/3, und addieren mit dem kgV als Hauptnenner, 1/12 + 1/18 = 3/36 + 2/36 = 5/36; der Hauptnenner ist das kgV, nicht das Produkt, 36 statt 216. Verhältnisse: 24 zu 36 ist 2 zu 3, Mischungsverhältnisse, Übersetzungen, Bildformate, 1920 × 1080 hat den ggT 120 und das Seitenverhältnis 16 : 9. Aufteilen: 24 Äpfel und 36 Birnen in gleiche Tüten ohne Rest, der ggT 12 sagt, es gehen höchstens 12 Tüten mit je 2 Äpfeln und 3 Birnen. Takte: Zwei Busse fahren alle 12 und alle 18 Minuten vom selben Bahnhof, das kgV 36 sagt, wann sie wieder gleichzeitig abfahren; Zahnräder mit 24 und 36 Zähnen stehen nach 360 Zähnen, 15 und 10 Umdrehungen, wieder in der Ausgangsstellung. Fliesen: Ein Raum von 360 mal 240 cm wird mit quadratischen Fliesen ohne Schnitt gefüllt, wenn die Kantenlänge den ggT 120 teilt, also 120, 60, 40, 30 cm. Musik: Zwei Rhythmen mit 3 und 4 Schlägen treffen sich nach kgV 12. Und in der Kryptografie ist der ggT der Kern von RSA, wo zwei Zahlen teilerfremd sein müssen, ggT 1, damit der Schlüssel funktioniert. Verhältnisse auf eine Größe hochrechnen kann der Dreisatz-Rechner.

Sonderfälle und Rechenregeln

Zwei Zahlen mit ggT 1 heißen teilerfremd, 8 und 15 etwa, ihr kgV ist das Produkt 120. Ist eine Zahl ein Teiler der anderen, ist sie der ggT und die andere das kgV, 6 und 18 haben ggT 6 und kgV 18. Der ggT mit 0 ist die andere Zahl, das kgV mit 0 ist 0, Primzahlen sind nur zu ihren Vielfachen nicht teilerfremd, und für mehr als zwei Zahlen gilt die Produktregel ggT · kgV = a · b nicht mehr, bei 24, 36, 60 ist 12 · 360 = 4.320, aber 24 · 36 · 60 = 51.840. Negative Zahlen behandelt man wie ihre Beträge, der Rechner nimmt positive ganze Zahlen. Teilbarkeitsregeln beschleunigen die Zerlegung: durch 2, wenn die letzte Ziffer gerade ist, durch 3, wenn die Quersumme durch 3 teilbar ist, durch 4, wenn die letzten zwei Ziffern durch 4 teilbar sind, durch 5 bei 0 oder 5 am Ende, durch 9 bei Quersumme durch 9, durch 11 bei alternierender Quersumme 0 oder durch 11 teilbar, und durch 6, 12, 15 als Kombination. Der erweiterte euklidische Algorithmus liefert nebenbei Zahlen x und y mit a · x + b · y = ggT, bei 12 und 18 zum Beispiel 12 · (-1) + 18 · 1 = 6, das Lemma von Bézout, das in der Zahlentheorie und beim Rechnen mit Resten überall gebraucht wird. Wie man Potenzen wie 2³ und 3² ausrechnet, zeigt der Potenzrechner.

Ein Stück Geschichte: Der älteste Algorithmus der Welt

Der euklidische Algorithmus steht im siebten Buch der "Elemente", die Euklid um 300 v. Chr. in Alexandria schrieb, als Satz 1 und 2: Man ziehe die kleinere Zahl von der größeren ab, so oft es geht, und fahre mit dem Rest fort, "Wechselwegnahme", und er bewies damit, dass jede Zahl eindeutig in Primfaktoren zerfällt, lange bevor Gauß 1801 den Fundamentalsatz der Arithmetik sauber formulierte. Das Verfahren ist wahrscheinlich älter, Aristoteles erwähnt es, und in China beschreibt das "Jiuzhang Suanshu" um 100 v. Chr. dieselbe Methode zum Kürzen von Brüchen. Knuth nannte ihn "den Großvater aller Algorithmen", weil er der älteste ist, der bis heute unverändert in Gebrauch ist; Lamé bewies 1844, dass er höchstens fünfmal so viele Schritte braucht, wie die kleinere Zahl Stellen hat, eine der ersten Laufzeitabschätzungen überhaupt. Das kgV brauchten die Astronomen für Kalender: Der Meton-Zyklus von 19 Jahren, 432 v. Chr., ist das Nahezu-kgV von Sonnenjahr und Mondmonat, 235 Monate gleich 19 Jahre, und die Berechnung des Osterdatums ist bis heute eine kgV-Aufgabe mit 19 und 28. Die Begriffe "größter gemeinsamer Teiler" und "kleinstes gemeinsames Vielfaches" prägte die deutsche Schulmathematik des 19. Jahrhunderts, die Abkürzungen ggT und kgV sind seit etwa 1900 üblich. Der Rechner rechnet Euklids Wechselwegnahme, nur mit Division statt Subtraktion.

Praktische Tipps

Nutzen Sie die Primfaktorzerlegung, wenn Sie den Weg zeigen müssen, und den euklidischen Algorithmus, wenn Sie nur die Zahl brauchen. Prüfen Sie bei zwei Zahlen mit ggT · kgV = a · b. Kürzen Sie Brüche immer mit dem ggT, dann ist es in einem Schritt getan, und nehmen Sie das kgV als Hauptnenner, nicht das Produkt. Lernen Sie die Teilbarkeitsregeln für 2, 3, 4, 5, 9 und 11. Bei mehr als zwei Zahlen rechnen Sie paarweise, ggT(ggT(a, b), c). Und tippen Sie in den Rechner beliebig viele Zahlen, durch Leerzeichen getrennt. Für Brüche mit dem gefundenen Hauptnenner geht es im Bruchrechner weiter.