Was ist der größte gemeinsame Teiler?

Der größte gemeinsame Teiler, abgekürzt ggT, ist die größte positive ganze Zahl, die zwei ganze Zahlen ohne Rest teilt. Für 1071 und 462 lautet sie 21: 1071 geteilt durch 21 ergibt 51, 462 geteilt durch 21 ergibt 22. Kein größerer positiver Teiler besitzt diese Eigenschaft.

Der ggT hilft beim Kürzen von Brüchen, beim Vereinfachen von Verhältnissen und beim Lösen zahlentheoretischer Gleichungen. Er beschreibt eine gemeinsame ganzzahlige Struktur. Bei Längen kann er beispielsweise die größtmögliche gleich große Abschnittslänge bestimmen, wenn beide Gesamtlängen exakt aufgeteilt werden sollen.

Die Reihenfolge der beiden Zahlen ändert das Ergebnis nicht: ggT(a,b) = ggT(b,a). Vorzeichen spielen ebenfalls keine Rolle, weil Teiler üblicherweise positiv angegeben werden. Deshalb verarbeitet der Rechner intern die Beträge der Eingaben, zeigt die Bézout-Koeffizienten aber passend zu den ursprünglichen Vorzeichen.

Euklidischer Algorithmus

Der euklidische Algorithmus ersetzt ein Zahlenpaar wiederholt durch den kleineren Wert und den Rest einer Division. Entscheidend ist die Identität ggT(a,b) = ggT(b, a mod b). Ein gemeinsamer Teiler von a und b teilt auch den Rest a − q·b; umgekehrt teilt ein gemeinsamer Teiler von b und dem Rest auch a.

Für 1071 und 462 beginnt die Rechnung mit 1071 = 2·462 + 147. Danach wird 462 durch 147 geteilt: 462 = 3·147 + 21. Schließlich gilt 147 = 7·21 + 0. Sobald der Rest null ist, ist der letzte von null verschiedene Rest der ggT, hier 21.

Rechenregel: Solange b nicht null ist, setze vorübergehend r = a mod b, dann a = b und b = r. Der zuletzt verbleibende positive Wert ist der ggT.

Diese Methode ist erheblich effizienter als alle Teiler beider Zahlen aufzuschreiben. Selbst bei großen Eingaben sinken die Reste schnell. Der Rechner begrenzt die Beträge trotzdem auf sichere ganze JavaScript-Zahlen, damit Divisionsreste und angezeigte Identitäten exakt bleiben.

ggT durch Primfaktorzerlegung

Alternativ können beide Zahlen in Primfaktoren zerlegt werden. Der ggT enthält jede gemeinsame Primzahl mit dem kleineren der beiden Exponenten. Beispielsweise ist 84 = 2²·3·7 und 126 = 2·3²·7. Gemeinsame Faktoren sind 2¹, 3¹ und 7¹, somit beträgt der ggT 42.

Die Primfaktorzerlegung ist anschaulich, wenn die Faktoren leicht erkennbar sind. Für große Zahlen kann das Faktorisieren jedoch viel aufwendiger als der euklidische Algorithmus sein. Um den ggT zu bestimmen, muss man die Primfaktoren gar nicht kennen.

Die Methode erklärt zugleich das kleinste gemeinsame Vielfache: Es übernimmt für jede vorkommende Primzahl den größeren Exponenten. Im Beispiel ergibt sich kgV(84,126) = 2²·3²·7 = 252. Das Produkt von ggT und kgV entspricht bei zwei positiven Zahlen dem Produkt der Zahlen.

Kleinstes gemeinsames Vielfaches

Das kleinste gemeinsame Vielfache, kurz kgV, ist die kleinste positive Zahl, die ein Vielfaches beider Eingaben ist. Der Rechner nutzt die Beziehung kgV(a,b) = |a·b|/ggT(a,b). Um unnötigen Zahlenüberlauf zu vermeiden, wird zuerst a durch den ggT geteilt und erst dann mit b multipliziert.

Für 1071 und 462 ergibt sich 1071/21 · 462 = 51·462 = 23.562. Diese Zahl ist sowohl durch 1071 als auch durch 462 ohne Rest teilbar. Das kgV eignet sich etwa für wiederkehrende Zyklen: Ein Ereignis alle 12 Tage und ein anderes alle 18 Tage fallen nach kgV(12,18) = 36 Tagen wieder zusammen.

Ist eine Eingabe null, wird das kgV üblicherweise als null definiert. Der ggT von null und einer von null verschiedenen Zahl ist der Betrag der anderen Zahl. Nur ggT(0,0) ist in der elementaren Definition nicht eindeutig; der Rechner kennzeichnet diesen Fall als nicht definiert.

Brüche und Verhältnisse kürzen

Ein Bruch a/b wird vollständig gekürzt, indem Zähler und Nenner durch ggT(|a|,|b|) geteilt werden. Aus 462/1071 wird nach Division durch 21 der Bruch 22/51. Zähler und Nenner sind danach teilerfremd, ihr ggT beträgt eins.

Dasselbe Prinzip gilt für Verhältnisse. Ein Format von 1920 zu 1080 Pixeln hat den ggT 120 und vereinfacht sich zu 16:9. Die vereinfachte Angabe bewahrt die Proportion, zeigt aber die kleinsten ganzzahligen Bestandteile.

Bei Einheiten müssen beide Größen vor dem Kürzen gleichartig sein. 2 Meter zu 50 Zentimeter darf nicht als 2:50 gekürzt werden; nach Umrechnung in Zentimeter lautet das Verhältnis 200:50 = 4:1. Der ggT prüft keine Einheiten und kann einen sachlichen Eingabefehler nicht erkennen.

Bézout-Identität und erweiterter Euklid

Für ganze Zahlen a und b, die nicht beide null sind, existieren ganze Zahlen x und y mit a·x + b·y = ggT(a,b). Diese Aussage heißt Bézout-Identität. Der erweiterte euklidische Algorithmus berechnet die Koeffizienten gleichzeitig mit dem ggT.

Im Beispiel ist −3·1071 + 7·462 = 21. Tatsächlich ergibt −3213 + 3234 genau 21. Die Koeffizienten sind nicht eindeutig: Addiert man zu x ein Vielfaches von b/ggT und zieht von y dasselbe Vielfache von a/ggT ab, bleibt die Summe gleich.

Bézout-Koeffizienten sind wichtig für modulare Inversen und lineare diophantische Gleichungen. Wenn ggT(a,m) = 1, ist der Koeffizient von a eine multiplikative Inverse modulo m. In Kryptografie und Codierungstheorie ist diese scheinbar einfache Rechnung deshalb ein grundlegender Baustein.

Teilerfremde Zahlen

Zwei Zahlen heißen teilerfremd, wenn ihr ggT eins ist. Sie müssen nicht selbst Primzahlen sein. Acht und neun sind zusammengesetzt beziehungsweise eine Potenz, teilen aber keinen positiven Faktor außer eins. Ebenso können zwei Primzahlen selbstverständlich teilerfremd sein, sofern sie verschieden sind.

Ein vollständig gekürzter Bruch hat teilerfremden Zähler und Nenner. In der modularen Arithmetik besitzt a genau dann eine Inverse modulo m, wenn a und m teilerfremd sind. Das ist eine stärkere Aussage als nur „a ist nicht durch m teilbar“.

Aufeinanderfolgende ganze Zahlen n und n+1 sind immer teilerfremd. Jeder gemeinsame Teiler müsste auch ihre Differenz eins teilen. Diese kleine Beobachtung ist ein typisches Beispiel dafür, wie Differenzen die ggT-Analyse vereinfachen.

Negative Zahlen und Null

Ein negatives Vorzeichen gehört beim Kürzen gewöhnlich in den Zähler oder vor den gesamten Bruch. Der positive ggT ändert das Vorzeichen nicht, sondern reduziert nur die Beträge. Das Ergebnis −6/8 wird zu −3/4.

Anwendungen in Geometrie und Planung

Ein 84 mal 126 Zentimeter großes Rechteck soll ohne Verschnitt in möglichst große gleich große Quadrate zerlegt werden. Die Seitenlänge eines Quadrats muss beide Maße teilen. Der größte mögliche Wert ist ggT(84,126) = 42 Zentimeter. Es entstehen zwei Reihen und drei Spalten, also sechs Quadrate.

Bei periodischen Abläufen wird dagegen häufig das kgV benötigt. Zwei Wartungsaufgaben im Rhythmus von 14 und 20 Tagen treffen nach 140 Tagen wieder zusammen. ggT und kgV beantworten verwandte, aber gegensätzliche Fragen: größtes gemeinsames Maß gegenüber kleinstem gemeinsamen Wiederholungspunkt.

Auch beim Skalieren digitaler Bilder hilft der ggT, ein Seitenverhältnis in kleinste ganze Zahlen zu überführen. Er sagt jedoch nichts über Bildqualität, Auflösung oder zulässige Druckgrößen. Die mathematische Vereinfachung muss immer in den Anwendungskontext eingeordnet werden.

Kontrollen und typische Fehler

• Der ggT muss beide Zahlen ohne Rest teilen.
• Bei positiven Zahlen gilt ggT·kgV = a·b.
• Das gekürzte Verhältnis muss denselben Quotienten besitzen.
• In der Bézout-Zeile muss die linke Seite exakt den ggT ergeben.
• Der letzte von null verschiedene Rest ist der ggT, nicht der erste Rest.
• Einheiten müssen vor einer Verhältnisbildung vereinheitlicht werden.

Ein häufiger Rechenfehler entsteht bei der Division mit Rest: Der Quotient muss ganzzahlig sein und der nichtnegative Rest kleiner als der Divisor. Bei negativen Eingaben arbeitet die sichtbare Schrittliste deshalb mit Beträgen. Dadurch entspricht sie der üblichen schulischen Darstellung.

Genauigkeitsgrenze: Der Rechner akzeptiert nur sichere ganze JavaScript-Zahlen. Bei extrem großen Ganzzahlen ist eine Big-Integer- oder Computer-Algebra-Software erforderlich.

Mehr als zwei Zahlen bearbeiten

Für drei oder mehr ganze Zahlen wird der ggT schrittweise gebildet. Zuerst berechnet man d = ggT(a,b), danach ggT(d,c) und so weiter. Wegen der Assoziativität ist die Klammerung unerheblich. Für 24, 36 und 60 gilt zunächst ggT(24,36)=12 und anschließend ggT(12,60)=12.

Das Ergebnis beschreibt den größten positiven Wert, der jede Zahl der Liste teilt. Soll eine Menge verschieden langer Bretter in gleich große maximal lange Abschnitte ohne Rest zerlegt werden, ist genau dieser Mehrfach-ggT gesucht. Der vorliegende Rechner besitzt zwei Eingabefelder; weitere Werte lassen sich nacheinander mit dem jeweils angezeigten Ergebnis kombinieren.

Auch das kgV mehrerer Zahlen kann iterativ bestimmt werden. Dabei wachsen Zwischenwerte schnell. Prüfen Sie vor praktischen Anwendungen, ob wirklich gemeinsame Abschnittslänge oder gemeinsamer Wiederholungszeitpunkt gefragt ist. Der ggT wird bei einer zusätzlichen Zahl gleich bleiben oder kleiner, das kgV gleich bleiben oder größer. Diese Richtung ist eine hilfreiche Plausibilitätskontrolle.

Häufige Fragen zum ggT

References

• Wolfram MathWorld – Greatest Common Divisor
• Wolfram MathWorld – Euclidean Algorithm
• Wolfram MathWorld – Bézout’s Identity