DE

ggT und kgV mehrerer Zahlen berechnen

Der ggT (größter gemeinsamer Teiler) und das kgV (kleinstes gemeinsames Vielfaches) werden meist für zwei Zahlen berechnet. Für eine Liste mehrerer Zahlen gilt dasselbe Prinzip: man reduziert die Liste Schritt für Schritt paarweise, wobei bei jedem Schritt der euklidische Algorithmus angewendet wird. Beliebig viele Zahlen lassen sich eingeben, getrennt durch Komma oder Leerzeichen.

Die Zahlenliste

Positive ganze Zahlen

2 bis 20 streng positive ganze Zahlen, getrennt durch Komma oder Leerzeichen.

Fachwörter mit Sternchen stehen im Glossar unten.

Größter gemeinsamer Teiler, kleinstes gemeinsames Vielfaches

Zwei positive ganze Zahlen teilen sich oft mehr als die 1. 12 und 18 haben die gemeinsamen Teiler 1, 2, 3 und 6. Der größte davon — 6 — ist der ggT*. Dieselbe Paarung hat gemeinsame Vielfache 36, 72, 108…; das kleinste, 36, ist das kgV*.

Der ggT misst, was sich noch gemeinsam herausziehen lässt. Das kgV misst, wo sich die Vielfachenketten zum ersten Mal treffen. Beides hängt an denselben Primfaktoren, beantwortet aber gegensätzliche Fragen: Wie weit lässt sich kürzen? Wann fällt der Takt wieder zusammen?

In der Mittelstufe stehen zuerst Teilerlisten und Vielfachenlisten an der Tafel. Das funktioniert, solange die Zahlen klein bleiben. Sobald drei, vier oder zwanzig Werte in einer Zeile stehen, wird das Listenführen unübersichtlich. Dann rechnet man nicht mehr „alle Teiler von 12, alle Teiler von 18, Schnittmenge“, sondern mit einem Verfahren, das ohne Aufzählung auskommt.

Division mit Rest: so läuft der euklidische Algorithmus

Jede Division ganzer Zahlen hinterlässt einen Rest, der streng kleiner ist als der Teiler. Genau das nutzt der euklidische Algorithmus*. Die größere Zahl durch die kleinere teilen, den Rest behalten, und dasselbe Spiel mit der alten kleineren Zahl und diesem Rest wiederholen. Landet der Rest bei null, war der letzte Teiler der ggT.

Jede Zeile hat die Gestalt a = q·b + r mit 0 ≤ r < b. Anschließend rückt b an die Stelle von a und r an die Stelle von b. Ein Paar, das unerwartet lange braucht: 144 und 89, zwei aufeinanderfolgende Fibonacci-Zahlen*.

  1. 144 = 1·89 + 55
  2. 89 = 1·55 + 34
  3. 55 = 1·34 + 21
  4. 34 = 1·21 + 13
  5. 21 = 1·13 + 8
  6. 13 = 1·8 + 5
  7. 8 = 1·5 + 3
  8. 5 = 1·3 + 2
  9. 3 = 1·2 + 1
  10. 2 = 2·1 + 0

Letzter Rest ungleich null: 1. Also ggT(144, 89) = 1. Zehn Zeilen für zwei bescheidene Zahlen — darauf kommt die Schrittzahl später zurück.

a = q·b + r  (wiederholt bis r = 0; der letzte Rest ungleich null ist der ggT)

Warum endet das immer? Die Reste sind natürliche Zahlen und werden streng kleiner. Eine unendliche, streng fallende Folge nichtnegativer ganzer Zahlen gibt es nicht. Irgendwann steht eine Null da. Meist sehr bald. Diese Seite schreibt jede Zeile auf, Paar für Paar, für Listen von 2 bis 20 positiven ganzen Zahlen.

Eine Liste paarweise zusammenziehen

Der ggT von drei Zahlen ist keine dritte Rechenart. Es ist die größte positive ganze Zahl, die alle drei teilt. Die Assoziativität reicht, um ihn mit dem Zweier-ggT auszurechnen.

ggT(a, b, c) = ggT(ggT(a, b), c)

kgV(a, b, c) = kgV(kgV(a, b), c)

Die ersten beiden verarbeiten, das Ergebnis mit der nächsten Zahl kombinieren, fertig. Die Reihenfolge in der Liste spielt keine Rolle. Beim kgV gilt in jedem Schritt die Zweierformel

kgV(a, b) = a · b ÷ ggT(a, b)

Für 15, 25, 35: ggT(15, 25) = 5, dann ggT(5, 35) = 5. Vielfache: kgV(15, 25) = 75, dann kgV(75, 35) = 525. Fünf teilt alle drei, nichts Größeres tut das; 525 ist das kleinste gemeinsame Vielfache. Zwanzig Zahlen heißen neunzehn solche Reduktionen — genau das, was das Formular durchläuft, mit jeder Division a = q·b + r im Protokoll. Beim kgV wird erst geteilt, dann multipliziert, damit Zwischenergebnisse nicht unnötig groß werden.

Primfaktorzerlegung als Schulweg

Solange die Zahlen klein bleiben, zerlegt die Schulmethode jede Zahl in Primfaktoren und liest die Exponenten ab.

Für den ggT den kleinsten Exponenten jeder Primzahl behalten. Für das kgV den größten. Eine Primzahl, die nur in einer Zerlegung vorkommt, fällt aus dem ggT und bleibt im kgV.

72 und 108:

  • 72 = 23 × 32
  • 108 = 22 × 33
  • ggT = 22 × 32 = 36
  • kgV = 23 × 33 = 216

Anschaulich. Unbrauchbar, sobald die Zahlen fünf- oder sechsstellig werden: 999 983 zu faktorisieren ist mühsam, Euklid ist nach ein paar Resten fertig. Deshalb rechnet diese Seite euklidisch, nicht über die Zerlegung. In der Mittelstufe bleibt die Zerlegung trotzdem der erste Weg, weil sie den Zusammenhang mit den Teilbarkeitsregeln sichtbar macht: wer die Zweier und Dreier zählt, sieht sofort, ob 8 oder 9 noch teilt.

Teilerfremde Zahlen

Zwei ganze Zahlen heißen teilerfremd*, wenn 1 ihr einziger positiver gemeinsamer Teiler ist. Keine von beiden muss eine Primzahl sein. 9 und 28 sind teilerfremd, 8 und 15 ebenfalls, 35 und 12 auch.

Aufeinanderfolgende ganze Zahlen sind immer teilerfremd. Jeder gemeinsame Teiler von n und n+1 würde auch die Differenz 1 teilen. Mehr Argument braucht es nicht.

Bei mehr als zwei Zahlen heißt „im Ganzen teilerfremd“ nur ggT(a, b, c, …) = 1. Das ist schwächer als „paarweise teilerfremd“. 6, 10 und 15 haben als Tripel den ggT 1, aber ggT(6, 10) = 2. Ein globaler ggT von 1 verbietet also nicht, dass einzelne Paare noch einen Faktor teilen. In Klausuren der Oberstufe wird dieser Unterschied gelegentlich abgefragt; wer ihn verwechselt, hält 6, 10, 15 für vollständig „ohne gemeinsamen Teiler“ und liegt daneben.

Brüche kürzen und den Hauptnenner setzen

Ein Bruch ist vollständig gekürzt, wenn Zähler und Nenner durch ihren ggT geteilt sind. Sonst nichts. Der Bruchrechner tut genau das; hier liegt der Teiler offen.

35/15, ein kleines Paar: ggT(35, 15) = 5, also

35 / 15 = (35 ÷ 5) / (15 ÷ 5) = 7 / 3

7 und 3 sind teilerfremd, weiter kürzen geht nicht. War der ggT von Anfang an 1, war der Bruch schon vollständig gekürzt — ein Test, nicht nur ein Rezept.

Durch einen gemeinsamen Teiler zu kürzen, der nicht der ggT ist, reicht nicht. 48/18 durch 2 ist 24/9, und 24/9 geht noch weiter. Erst der ggT (6) liefert 8/3.

Denselben Apparat braucht die Addition. 1/6 + 1/8 + 1/10 verlangt einen gemeinsamen Nenner. Jedes gemeinsame Vielfache von 6, 8 und 10 tut es (240, 480…); das sparsamste ist ihr kgV — in der Schule der Hauptnenner*. kgV(6, 8, 10) = 120, also 20/120 + 15/120 + 12/120 = 47/120. Der ggT von 47 und 120 ist 1, der Bruch bleibt. ggT und kgV reichen sich die Arbeit zu.

Gemeinsame Takte: Fahrpläne, Zahnräder, Perioden

Das kgV beantwortet: wann treffen sich diese Perioden wieder?

S-Bahn alle 10 Minuten, Bus alle 15, beide fahren um 8:00 gemeinsam ab. Das nächste gemeinsame Abfahren ist nach kgV(10, 15) = 30 Minuten, also 8:30. Drei Ampeln mit 12, 18 und 20 Sekunden sind gemeinsam grün alle kgV(12, 18, 20) = 180 Sekunden. Zwei Zahnräder mit 15 und 25 Zähnen stehen nach 75 Zähnen wieder in der Ausgangslage — dieselbe Rechnung, andere Werkstatt.

Mehr als zwei Perioden: wieder paarweise falten. Sind die Zeiten nicht ganzzahlig (alle 2,5 min und alle 4 min), zuerst auf eine gemeinsame Einheit gehen — hier halbe Minuten: 5 und 8. Das Formular nimmt nur streng positive ganze Zahlen; die Umrechnung gehört vor die Eingabe.

Bézout-Identität und lineare ganzzahlige Gleichungen

Die Bézout-Identität* sagt: zu zwei ganzen Zahlen a und b gibt es immer ganze Zahlen u und v — auch negative — mit

a·u + b·v = ggT(a, b)

Für 35 und 15 reicht u = 1, v = −2: 35·1 + 15·(−2) = 35 − 30 = 5. Die Koeffizienten liest man, indem man die euklidischen Reste rückwärts auflöst (erweiterter euklidischer Algorithmus). Modulare Inverse, lineare diophantische Gleichungen*, ein Stück elementare Kryptographie: dafür braucht es u und v.

Im Leistungskurs Mathematik taucht das als ganzzahlige Linearkombination auf, selten unter dem Namen Bézout. Die Gleichung 12x + 18y = 30 hat ganzzahlige Lösungen, weil ggT(12, 18) = 6 die 30 teilt. 12x + 18y = 25 hat keine, weil 6 die 25 nicht teilt. Das ist der ganze Existenzsatz, in einem Satz.

Diese Seite gibt u und v nicht aus und bleibt beim ggT, beim kgV und bei den Divisionsschritten. Die Bézout-Koeffizienten sind eine zweite Lesart derselben Reste, kein Formularfeld.

ggT oder GGT: die Schreibweise in Mittelstufe und Abitur

In deutschen Schulbüchern steht heute fast immer ggT und kgV — drei Kleinbuchstaben, die Anfangsbuchstaben der Wörter. Ältere Ausgaben, mancher Tafelanschrieb und vereinzelte Arbeitsblätter schreiben GGT und KGV. Beides meint dieselbe Größe. Was in der Klausur zählt, ist die Konsistenz, nicht die Großschreibung.

Falsch wäre Ggt, KgV oder eine Mischung in einer Zeile. Die Funktionsklammern gehören dazu, sobald Argumente dastehen: ggT(12, 18, 30), nicht „ggT von 12, 18 und 30“ als einzige Form. Programmiersprachen verwenden gcd und lcm; das ist Englisch, kein deutscher Tafeltext.

In der Mittelstufe (Klassen 5 bis 7) reicht die Definition über Teiler- und Vielfachenlisten plus die Primfaktorzerlegung. Der euklidische Algorithmus kommt später, oft erst wenn die Mathematik-Übersicht Richtung Zahlentheorie kippt — Wahlpflicht, Vertiefung, Leistungskurs. Das Abitur selbst fragt den ggT selten als Selbstzweck; er steckt im Kürzen von Termen, im Hauptnenner rationaler Funktionen und gelegentlich in einer ganzzahligen Gleichung. Wer den Algorithmus hier Schritt für Schritt sieht, hat genau den Handgriff, den eine solche Aufgabe voraussetzt, ohne ihn auszuschreiben.

Fibonacci-Paare und die Schrittzahl

Euklid ist schnell. Die Schrittzahl wächst mit dem Logarithmus der Zahlen, nicht mit den Zahlen selbst.

Den ungünstigsten Fall hat Lamé 1844 bestimmt: zwei aufeinanderfolgende Fibonacci-Zahlen. Jeder Quotient ist 1, der Rest sinkt so langsam wie möglich. Genau das war das Paar 144 und 89 oben — zehn Reste, und am Ende ggT = 1. Für beliebige Eingaben gilt: die Anzahl der Divisionen ist höchstens das Fünffache der Dezimalstellenzahl der kleineren Zahl.

Deshalb ist „erst faktorisieren, dann Exponenten lesen“ maschinell fast immer die langsamere Idee. Fibonacci-Paare sind in diesem Rechner keine Falle; sie füllen nur die Tabelle.

Die Produktformel gilt nur für zwei Zahlen

Für ein Paar gilt stets ggT(a, b) × kgV(a, b) = a × b. Genau deshalb lässt sich das kgV berechnen, ohne Vielfache aufzulisten.

Auf drei Argumente lässt sich das nicht so übertragen. Bei 2, 4 und 8: ggT = 2, kgV = 8, Produkt der drei ist 64, und 2 × 8 = 16, nicht 64. Eine hübsche „globale“ Produktformel dieser Form gibt es nicht.

Und ein ggT von drei Zahlen ist auch keine Extra-Operation. ggT(a, b, c) ist ggT(ggT(a, b), c). Diese Seite faltet von links nach rechts, weil die Operation assoziativ (und kommutativ) ist. Die Reihenfolge in der Eingabe ändert das Ergebnis nicht.

Eine letzte Konvention, die hier nicht gilt: ggT(0, n) = n für n > 0. Null ist Vielfaches jeder ganzen Zahl, die gemeinsamen Teiler von 0 und n sind also genau die Teiler von n. ggT(0, 0) lässt man undefiniert. Dieser Rechner lehnt 0 ab, und negative Zahlen ebenso. Er erwartet 2 bis 20 streng positive ganze Zahlen unter 1.000.000. Euklid käme mit der Konvention klar; das kgV nicht. Jedes Vielfache von 0 ist 0, und „kleinstes gemeinsames Vielfaches“ wird dann ein Wortspiel, das hier nichts sucht.

Glossar

ggT
Größter gemeinsamer Teiler. Die größte positive ganze Zahl, die alle angegebenen Zahlen ohne Rest teilt. In älteren Texten auch GGT.
kgV
Kleinstes gemeinsames Vielfaches. Die kleinste positive ganze Zahl, die ein Vielfaches jeder angegebenen Zahl ist. In älteren Texten auch KGV.
Euklidischer Algorithmus
Verfahren, den ggT zweier ganzer Zahlen durch wiederholte Division mit Rest zu bestimmen. Der letzte Rest ungleich null ist der ggT. Die Schrittzahl wächst logarithmisch.
Teilerfremd
Zwei ganze Zahlen mit ggT 1. Keine von beiden muss eine Primzahl sein. Paarweise teilerfremd ist strenger als ein gemeinsamer ggT von 1 über die ganze Liste.
Hauptnenner
In der Schulsprache das kgV der Nenner, auf das Brüche gebracht werden, bevor sie addiert oder subtrahiert werden.
Bézout-Identität
Zu a und b existieren ganze Zahlen u, v mit a·u + b·v = ggT(a, b). Die Koeffizienten entstehen, indem man die euklidischen Reste rückwärts auflöst.
Diophantische Gleichung
Gleichung, bei der ganzzahlige Lösungen gesucht sind. Die lineare Form ax + by = c ist genau dann ganzzahlig lösbar, wenn der ggT von a und b die Zahl c teilt.
Fibonacci-Zahlen
Folge 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …; jedes Glied ist die Summe der beiden vorangehenden. Zwei Nachbarn sind der ungünstigste Fall für Euklid: jeder Quotient ist 1.

Das könnte Sie auch interessieren