Größter Gemeinsamer Teiler (ggT)

1. Zahl:
2. Zahl:

Über den Rechner

Mit diesem Rechner lässt sich der größte gemeinsame Teiler (kurz ggT) von 2 Zahlen berechnen. Es werden nur Zahlen akzeptiert, die größer als 0 sind. Den ggT kann man mit Hilfe einer Primfaktorzerlegung oder mit dem euklidischen Algorithmus berechnen. Dieser Rechner nutzt den euklidischen Algorithmus.

Was ist der ggT?

Größter gemeinsamer Teiler 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 und somit nicht der ggT.

Primfaktorzerlegung

Jede ganze Zahl größer als 0 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

Euklidischer 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 berechnen mit euklidischem Algorithmus

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=1Rest72
84:72=1Rest12
72:12=6Rest0

Ergebnis: ggT(156, 84) = 12

90:12=7Rest6
12:6=2Rest0

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.

Als Beispiel soll der Bruch
156
84
gekürzt werden. Dafür wird zuerst der ggT von 156 und 84 berechntet. Der ist 12. Danach werden sowohl die 156 als auch die 84 durch 12 geteilt und man erhält
13
7
.

gute Erklärvideos auf YouTube:

Ähnliche Themen

Berechnung speichern

URL der Berechnung:

Seite teilen: Facebook Twitter