Über den Rechner
Mit diesem Rechner lässt sich der größte gemeinsame Teiler (kurz ggT) von 2 oder mehr Zahlen berechnen. Es werden nur Zahlen akzeptiert, die größer als 0 sind. Es kann ausgewählt werden, ob der ggT mit der Hilfe von Primfaktorzerlegungen oder mit dem euklidischen Algorithmus berechnet werden soll. Der größte gemeinsame Teiler kann für das Kürzen von Brüchen verwendet werden.
Was ist der größte gemeinsame Teiler?
Der größte gemeinsame Teiler (kurz ggT) von 2 Zahlen ist die größte natürliche Zahl, durch die sich beide Zahlen ohne Rest teilen lassen.
Zum Beispiel ist 4 der ggT von 12 und 16. 2 ist auch ein Teiler von 12 und 16, aber nicht der Größte.
ggT mit Primfaktorzerlegungen
Jede ganze Zahl größer als 1 ist entweder selber eine Primzahl oder lässt sich als Produkt von Primzahlen darstellen. Die einzelnen Zahlen dieses Produkts nennt man Primfaktoren.
Zum Beispiel lautet die Primfaktorzerlegung der Zahl 156: 2 · 2 · 3 · 13
Und für die Zahl 84: 2 · 2 · 3 · 7
Um den ggT zu bestimmen, müssen aus beiden Primfaktorzerlegungen die gemeinsamen Primfaktoren ermittelt werden und aus diesen wird das Produkt gebildet. Wichtig ist, dass wenn eine Zahl mehrfach in beiden Primfaktorzerlegungen vorkommt, dann kommt sie auch mehrfach im Produkt vor.
Die gemeinsamen Primfaktoren der Primfaktorzerlegungen von 156 und 84 sind: 2, 2, 3
Somit ist der ggT 2 · 2 · 3 = 12
ggT mit Euklidischem Algorithmus
Beim euklidischen Algorithmus wird zuerst die größere Zahl durch die kleinere Zahl mit Rest geteilt. Wenn ein Rest übrig bleibt, wird die frühere kleinere Zahl (Divisor) zur neuen großen Zahl (Divident) und der Rest zur neuen kleineren Zahl (Divisor). Dies wird so lange gemacht, bis der Rest 0 ist. Der ggT ist dann die kleinere Zahl.
Beispiel:
Als Beispiel sollen wieder der größte gemeinsame Teiler der Zahlen 84 und 156 berechnet werden.
Im ersten Schritt wird 156 (die größere Zahl) durch 84 (die kleinere Zahl) mit Rest geteilt.
156:84=1Rest72
Der Rest ist noch nicht 0. Deshalb muss noch weiter gerechnet werden. Nun wird die 84 durch den Rest (also die 72) geteilt.
84:72=1Rest12
Der Rest ist wieder ungleich 0. Also wird wieder die vorherige kleinere Zahl (72) durch den Rest (12) geteilt.
72:12=6Rest0
Als Rest ist 0 herausgekommen. Das heißt, dass der größte gemeinsame Teiler gefunden wurde. Der ggT ist aus der letzten Berechnung die Zahl, durch die geteilt wurde. Also 12.
ggT von mehr als 2 Zahlen
Aber wie berechnet man den größten gemeinsamen Teiler von mehr als 2 Zahlen?
Primfaktorzerlegung:
Das Bestimmen des ggT von mehr als 3 Zahlen mit der Hilfe der Primfaktorzerlegung funktioniert genau so, wie auch mit 2 Zahlen. Man bestimmt für jede Zahl die Primfaktoren, ermittelt daraus die gemeinsamen Primfaktoren und bildet davon das Produkt.
Beispiel:
Es soll der ggT von 156, 84 und 90 ermittelt werden.
Primfaktorzerlegung von 156: 2 · 2 · 3 · 13
Primfaktorzerlegung von 84: 2 · 2 · 3 · 7
Primfaktorzerlegung von 90: 2 · 3 · 3 · 5
Die gemeinsamen Primfaktoren sind: 2 und 3
Somit gilt: ggT(156, 84, 90) = 2 · 3 = 6
euklidischer Algorithmus:
Der euklidische Algorithmus funktioniert immer nur mit 2 Zahlen gleichzeitig. Was man aber machen kann ist, dass man den Algorithmus zuerst auf 2 Zahlen anwendet und den Algorithmus danach auf das Ergebnis und die nächste Zahl anwendet. Dabei ist egal, in welcher Reihenfolge man dies macht.
Wenn man 3 Zahlen a, b und c hat, kann man zum Beispiel zuerst ggT(a, b) = z berechnen und danach ggT(z, c), um den ggT von allen 3 Zahlen zu erhalten. Man könnte aber auch zuerst den ggT von b und c bestimmen und danach mit dem Zwischenergebnis und a den ggT von allen 3 Zahlen.
Es gilt:
ggT(a, b, c) = ggT(ggT(a, b), c) = ggT(ggT(a, c), b) = ggT(ggT(b, c), a)
Beispiel:
Es soll wieder der ggT von 156, 84 und 90 ermittelt werden.
Zuerst wird der ggT von 156 und 84 mit dem euklidischem Algorithmus bestimmt und danach der ggT vom Zwischenergebnis und 90:
| 156 | : | 84 | = | 1 | Rest | 72 |
| 84 | : | 72 | = | 1 | Rest | 12 |
| 72 | : | 12 | = | 6 | Rest | 0 |
Ergebnis: ggT(156, 84) = 12
| 90 | : | 12 | = | 7 | Rest | 6 |
| 12 | : | 6 | = | 2 | Rest | 0 |
Ergebnis: ggT(12, 90) = 6
Es gilt also ggT(156, 84, 90) = ggT(ggT(156, 84), 90) = 6.
Was kann man mit dem ggT machen?
Den größten gemeinsamen Teiler kann man unter anderem dafür benutzen Brüche zu kürzen. Dafür berechnet man einfach den ggT vom Zähler und vom Nenner und teilt danach sowohl den Zähler als auch den Nenner durch den ggT.
| 156 |
| 84 |
| 13 |
| 7 |