ggT-Rechner

Q: Was ist der ggT einer Zahl und 0?

Jede ganze Zahl teilt 0, also gilt gcd(a, 0) = |a|. Der ggT von 0 und 0 ist nicht definiert.

Über den ggT-Rechner

Der größte gemeinsame Teiler einer Menge ganzer Zahlen ist die größte positive ganze Zahl, die jede von ihnen ohne Rest teilt. Man braucht ihn zum Kürzen von Brüchen, zum Ausklammern in Termen und zum Aufteilen von Mengen in gleich große Gruppen.

Der Rechner zerlegt jede Zahl in Primfaktoren und wendet außerdem den euklidischen Algorithmus an, damit du ein anschauliches Verfahren mit dem schnellsten vergleichen kannst.

Was ist der größte gemeinsame Teiler?

Ein Teiler einer ganzen Zahl teilt sie ohne Rest: Die Teiler von 12 sind 1, 2, 3, 4, 6 und 12. Ein gemeinsamer Teiler mehrerer Zahlen teilt sie alle, und der größte gemeinsame Teiler ist der größte davon. Die Teiler von 18 sind 1, 2, 3, 6, 9 und 18, also sind die gemeinsamen Teiler von 12 und 18 die Zahlen 1, 2, 3 und 6, und der ggT ist 6.

Teiler aufzulisten klappt bei kleinen Zahlen, wird aber schnell mühsam. Primfaktorzerlegung und euklidischer Algorithmus finden den ggT ohne Liste, und beide funktionieren für beliebig viele Werte: Der ggT von drei Zahlen ist der ggT der ersten beiden, kombiniert mit der dritten.

So benutzt du den ggT-Rechner

Gib zwei bis zehn ganze Zahlen ein, getrennt durch Kommas oder Leerzeichen.
Klicke auf ggT berechnen.
Sieh dir die Primfaktorzerlegung jeder Zahl, die gemeinsamen Primfaktoren und die Divisionen des euklidischen Algorithmus an.

Formeln

Euklidischer Algorithmus

\gcd(a, b) = \gcd(b,\ a \bmod b),\quad \gcd(a, 0) = a

Aus der Primfaktorzerlegung

\gcd = \prod p^{\min(e_1, e_2, \ldots)}

Jeder gemeinsame Primfaktor wird mit seinem kleinsten Exponenten genommen.

Zusammenhang mit dem kgV

\gcd(a, b) \cdot \operatorname{lcm}(a, b) = |ab|

Durchgerechnetes Beispiel: 48, 180

Das durchgerechnete Beispiel bestimmt den ggT von 48 und 180. Die Primfaktorzerlegung liefert $48 = 2^4 \times 3$ und $180 = 2^2 \times 3^2 \times 5$ . Der euklidische Algorithmus teilt 180 durch 48 (Rest 36), dann 48 durch 36 (Rest 12), dann 36 durch 12 (Rest 0), also ist der ggT 12. Die gemeinsamen Primfaktoren mit dem kleinsten Exponenten, $2^2 \times 3 = 12$ , bestätigen das, und die Probe zeigt, dass 48 und 180 geteilt durch 12 die Zahlen 4 und 15 ergeben.

Die folgende Lösung wird von derselben Rechen-Engine erzeugt wie der Rechner oben.

Ergebnis

12

So haben wir deine Aufgabe verstanden

Den größten gemeinsamen Teiler (ggT) der Zahlen bestimmen.

Lösungsweg Schritt für Schritt

Primfaktorzerlegung jeder Zahl
$48 = 2^{4} \times 3,\quad 180 = 2^{2} \times 3^{2} \times 5$
Euklidischer Algorithmus für GCF(48, 180)
180 = 3 × 48 + 36; 48 = 1 × 36 + 12; 36 = 3 × 12 + 0
$180 = 3 \times 48 + 36 \\ 48 = 1 \times 36 + 12 \\ 36 = 3 \times 12 + 0$
Der letzte von null verschiedene Rest ist der ggT
$\gcd(48, 180) = 12$
Mit den gemeinsamen Primfaktoren bestätigen
Die Primfaktoren, die in allen Zahlen vorkommen, jeweils mit dem kleinsten Exponenten multiplizieren.
$2^{2} \times 3 = 12$

Verwendete Formeln

Euklidischer Algorithmus
$\gcd(a, b) = \gcd(b,\ a \bmod b),\quad \gcd(a, 0) = a$

12 ist die größte ganze Zahl, die jede der Zahlen ohne Rest teilt.

Probe

48 ÷ 12 = 4
180 ÷ 12 = 15

Ausführliche Erklärung

Warum der euklidische Algorithmus funktioniert

Jede Zahl, die $a$ und $b$ teilt, teilt auch $a - b$ und damit auch den Rest der Division von $a$ durch $b$ . Das Paar $(a, b)$ und das Paar $(b, a \bmod b)$ haben also genau dieselben gemeinsamen Teiler. Jeder Schritt verkleinert die Zahlen, und wenn der Rest 0 erreicht, teilt die verbleibende Zahl sich selbst und 0, ist also der größte gemeinsame Teiler. Das Verfahren braucht selbst bei sehr großen Zahlen nur wenige Divisionen und wird deshalb in der Computerarithmetik und in der Kryptografie eingesetzt.

Wofür man den ggT braucht

Teilt man Zähler und Nenner durch ihren ggT, ist ein Bruch in einem Schritt vollständig gekürzt: $\frac{48}{180} = \frac{4}{15}$ . In der Algebra klammert man als Erstes den ggT der Koeffizienten aus, wie in $12x + 18 = 6(2x + 3)$ . Bei Alltagsaufgaben beantwortet er Fragen wie die nach der größten Zahl gleicher Gruppen: 24 Bleistifte, 36 Radiergummis und 60 Aufkleber lassen sich auf höchstens 12 gleiche Päckchen verteilen, weil $\gcd(24, 36, 60) = 12$ .

Primfaktorzerlegung oder euklidischer Algorithmus

Die Primfaktorzerlegung zeigt die Struktur: Du siehst genau, welche Primfaktoren die Zahlen gemeinsam haben und warum das Ergebnis so ausfällt, was beim Lernen hilft oder wenn du auch das kgV brauchst. Die Schwäche: Große Zahlen zu zerlegen dauert lange. Der euklidische Algorithmus zerlegt gar nichts; er teilt nur und merkt sich die Reste, bleibt also auch bei Zahlen mit Dutzenden Stellen schnell. Der Rechner zeigt beide, damit das eine Verfahren das andere bestätigt.

Häufige Fehler

Alle vorkommenden Primfaktoren multiplizieren statt nur der gemeinsamen.
Bei einem gemeinsamen Primfaktor den größten Exponenten nehmen; der ggT verwendet den kleinsten.
Annehmen, es gebe keinen ggT, wenn die Zahlen teilerfremd sind; in diesem Fall ist der ggT 1.
Den euklidischen Algorithmus einen Schritt zu früh beenden und den letzten Quotienten statt des letzten von null verschiedenen Rests angeben.

Tipps

Teilt eine Zahl alle anderen, ist sie der ggT.
Der ggT zweier aufeinanderfolgender ganzer Zahlen ist immer 1.
Kürze einen Bruch mit dem ggT von Zähler und Nenner in einem einzigen Schritt.
Prüfe das Ergebnis, indem du jede Zahl dadurch teilst; die Quotienten dürfen außer 1 keinen gemeinsamen Teiler haben.
Bei drei oder mehr Zahlen berechnest du zuerst den ggT von zwei Zahlen und kombinierst das Ergebnis dann mit der nächsten Zahl.

Häufige Fragen

Was ist der größte gemeinsame Teiler?

Er ist die größte positive ganze Zahl, die alle Zahlen der Menge ohne Rest teilt. Für 48 und 180 ist er 12.

ggT, GCD, GCF, HCF: Ist das dasselbe?

Ja. Auf Deutsch sagt man ggT; im Englischen bezeichnen GCD, GCF und HCF dieselbe Zahl.

Wie funktioniert der euklidische Algorithmus?

Teile die größere Zahl durch die kleinere und merke dir den Rest. Ersetze das Paar durch (kleinere Zahl, Rest) und wiederhole das, bis der Rest 0 ist; der letzte von null verschiedene Divisor ist der ggT.

Was ist der ggT von Zahlen ohne gemeinsamen Teiler?

Er ist 1. Solche Zahlen heißen teilerfremd, zum Beispiel 8 und 15.

Kann man den ggT negativer Zahlen berechnen?

Ja. Die Teilbarkeit hängt nicht vom Vorzeichen ab: Der ggT wird mit den Beträgen berechnet und ist immer positiv.

Was ist der ggT einer Zahl und 0?

Jede ganze Zahl teilt 0, also gilt $\gcd(a, 0) = |a|$ . Der ggT von 0 und 0 ist nicht definiert.

Wie berechnet man den ggT von drei Zahlen?

Berechne den ggT von zwei Zahlen und dann den ggT dieses Ergebnisses mit der dritten. Für 24, 36 und 60: $\gcd(24, 36) = 12$ und $\gcd(12, 60) = 12$ .

Wie hilft der ggT beim Kürzen von Brüchen?

Teile Zähler und Nenner durch ihren ggT, dann ist der Bruch sofort vollständig gekürzt. Da $\gcd(48, 180) = 12$ gilt, ist $\frac{48}{180} = \frac{4}{15}$ .

Probiere den ggT-Rechner aus

Gib deine Zahlen ein und vergleiche die Primfaktorzerlegung mit dem euklidischen Algorithmus.

Rechner verwenden Den KI-Löser fragen

Über den ggT-Rechner

Was ist der größte gemeinsame Teiler?

So benutzt du den ggT-Rechner

Formeln

Euklidischer Algorithmus

Aus der Primfaktorzerlegung

Zusammenhang mit dem kgV

Durchgerechnetes Beispiel: 48, 180

Ergebnis

So haben wir deine Aufgabe verstanden

Lösungsweg Schritt für Schritt

Verwendete Formeln

Probe

Ausführliche Erklärung

Warum der euklidische Algorithmus funktioniert

Wofür man den ggT braucht

Primfaktorzerlegung oder euklidischer Algorithmus

Häufige Fehler

Tipps

Häufige Fragen

Was ist der größte gemeinsame Teiler?

ggT, GCD, GCF, HCF: Ist das dasselbe?

Wie funktioniert der euklidische Algorithmus?

Was ist der ggT von Zahlen ohne gemeinsamen Teiler?

Kann man den ggT negativer Zahlen berechnen?

Was ist der ggT einer Zahl und 0?

Wie berechnet man den ggT von drei Zahlen?

Wie hilft der ggT beim Kürzen von Brüchen?

Probiere den ggT-Rechner aus

Weitere Mathe-Rechner