Größter gemeinsamer Teiler (ggT)

Als "Teiler" einer ganzen Zahl \(x\) bezeichnet man eine natürliche Zahl, durch die sich \(x \) ohne Rest teilen lässt. Teiler listet man oft als Menge.

Beispiel:

Ein Teiler von \(20 \) ist \(2\), weil \(20:2=10\) Rest \(0\) ist. Alle Teiler sind \(1\), \(2\), \(4\), \(5\), \(10\) und \(20\) (als Menge: \(\{1;2;4;5;10;20\}\))

Der größte gemeinsame Teiler (=ggT) zweier oder mehrerer Zahlen ist die größte natürliche Zahl, durch die sich alle diese Zahlen teilen lassen.

Beispiel:

Die Teiler von \(20\) sind \(1\), \(2\), \(4\), \(5\), \(10\) und \(20\).

Die Teiler von \(30\) sind \(1\), \(2\), \(3\), \(5\), \(6\), \(10\), \(15\) und \(30\).

Der größte gemeinsame Teiler von \(20\) und \(30 \) ist \(10\), also kurz \(\text{ggT}(20;30)=10\)

Den ggT nutzt man beispielsweise beim Rechnen mit Brüchen. Dort ist es hilfreich, den \(\mathrm{ggT}\) von Zähler und Nenner zu bestimmen, um mit ihm zu kürzen.

Wie kommt man auf den \(\mathrm{ggT}\) ?

Im Folgenden werden dir 3 verschiedene Methoden zur Berechnung des ggTs vorgestellt:

• Teiler auflisten
• Über die Primfaktorzerlegung
• Über den euklidischen Algorithmus

Teiler auflisten

Diese Methode funktioniert bei kleinen Zahlen, bei denen man leicht überprüfen kann, welche Teiler sie haben.

Beispiel 1

Gesucht ist der \(\mathrm{ggT}\) von 16 und 20.

Die größte Zahl, die sowohl Teiler von \(16\) als auch von \(20\) ist, ist \(4\) \(\Rightarrow\) \(\mathrm{ggT}(16;20)=4\)

Beispiel 2

Gesucht ist der ggT von \(8\), \(12\) und \(30\).

Die größte Zahl, die sowohl Teiler von \(8\), \(12\) als auch von \(30\) ist, ist \(2\) \(\Rightarrow\) \(\mathrm{ggT}(8;12;30)=2\)

Video zur Bestimmung des ggt (Teiler auflisten)

Über die Primfaktorzerlegung

Hat man die Primfaktorzerlegung zweier (oder mehrerer) Zahlen, kann man daraus den größten gemeinsamen Teiler ausrechnen.

Beispiel 1

Gesucht ist \(\mathrm{ggT}(12;18)\) :

\(\begin{array}{rl}12&=&\textcolor{orange}{2}&\cdot2&\cdot\textcolor{orange}{3}\\18&=&\textcolor{orange}{2}&&\cdot \textcolor{orange}{3}&\cdot3\\\hline \text{ggT}(12;18)&=&\textcolor{orange}{2}&&\cdot \textcolor{orange}{3}&&=6\end{array}\)

Beide Zahlen haben die \(2\) und die \(3\) jeweils einfach als Primfaktoren gemeinsam.

Also ist \(\mathrm{ggT}(12;18)=2\cdot3=6\)

Beispiel 2

Gesucht ist \(\mathrm{ggT}(120;900)\) :

\(\begin{array}{rl}120&=&\textcolor{orange}{2}&\cdot\textcolor{orange}{2}&\cdot2&\cdot\textcolor{orange}{3}&&\cdot\textcolor{orange}{5}\\900&=&\textcolor{orange}{2}&\cdot\textcolor{orange}{2}&&\cdot\textcolor{orange}{3}&\cdot3&\cdot\textcolor{orange}{5}&\cdot5\\\hline\text{ggT}(120;900)&=&\textcolor{orange}{2}&\cdot\textcolor{orange}{2}&&\cdot\textcolor{orange}{3}&&\cdot\textcolor{orange}{5}&&=60\end{array}\)

Beide Zahlen haben die \(2\), \(3\) und \(5\) als Primfaktoren gemeinsam. Den Primfaktor \(2\) haben beide sogar zweimal gemeinsam.

Also ist \(\mathrm{ggT}(120;900)=2\cdot2\cdot3\cdot5=2^2\cdot3\cdot5=60\)

Beispiel 3

Gesucht ist \(\mathrm{ggT}(105;26)\) :

\(\begin{array}{rl}105&=&&3&\cdot5&\cdot7\\26&=&2&&&&\cdot13\\\hline\text{ggT}(105;26)&&&&&&&=1\end{array}\)

Die beiden Zahlen haben also keinen gemeinsamen Primfaktor. Deshalb ist \(\mathrm{ggT}(105;26)=1\)

Beispiel 4

Gesucht ist der \(\text{ggT}(10;15;90)\).

\(\begin{array}{rl}10&=&2&&&\cdot\textcolor{orange}{5}\\15&=&&3&&\cdot \textcolor{orange}{5}&&\\90&=&2&\cdot 3&\cdot 3&\cdot \textcolor{orange}{5}\\\hline\text{ggT}(10;15;90)&=&&&&\textcolor{orange}{5}\end{array}\)

Die drei Zahlen haben also den gemeinsamen Primfaktor \(5\). Deshalb ist \(\mathrm{ggT}(10;15;90)=5\)

Video zur Bestimmung des ggT (Primfaktorzerlegung)

Über den euklidischen Algorithmus

Mit dem euklidischen Algorithmus kann man den größten gemeinsamen Teiler auch ausrechnen. Mitunter ist es ein wenig langwierig, aber hat man die Methode einmal verstanden, führt sie einen auch für große Zahlen sicher zum Ziel.

Die Vorgehensweise mittels dieser Methode ist im folgenden Artikel erklärt: euklidischer Algorithmus

Es lässt sich hierdurch erstmal nur der ggT zweier Zahlen bestimmen. Möchtest du den ggT dreier (oder von noch mehr Zahlen) mithilfe dieser Methode berechnen, musst du mehrstufig vorgehen.

Beispiel: Gesucht ist der ggT von \(60\), \(90\) und \(100\). Berechne den ggT zweier Zahlen, z.B. \(\text{ggT}(60;90)=30\). Danach kannst du die Methode nochmal anwenden: