de
Seitenbanner
Menu
A-Z
  • Nachlesen
  • Zahlentheorie
  • Größter gemeinsamer Teiler (ggT)
Nachlesen

Größter gemeinsamer Teiler (ggT)

Beim größten gemeinsamen Teiler (ggT) handelt es sich um einen mathematischen Begriff, der unter anderem in den Gebieten der Arithmetik und der Zahlentheorie eine Rolle spielt. Es handelt sich dabei um die größte natürliche Zahl, durch die sich zwei gegebene ganze Zahlen ohne Rest teilen lassen. Das Gegenstück des größten gemeinsamen Teilers ist das kleinste gemeinsame Vielfache (kgV).

Der englische Begriff gcd (von greatest common divisor) ist ebenfalls verbreitet.

Inhalt

Berechnung

Berechnung des größten gemeinsamen Teilers mithilfe der Primfaktorzerlegung

Der größte gemeinsame Teiler zweier ganzer Zahlen kann über ihre Primfaktorzerlegung bestimmt werden. Hierfür werden zunächst alle Primfaktoren ermittelt, die in beiden Zerlegungen vorkommen, und anschließend in ihrer jeweils kleineren, vorkommenden Potenz multipliziert.

Beispiel

Es soll der größte gemeinsame Teiler von \(3780\) und \(7200\) berechnet werden. Es gilt

\begin{align*} 3780 &= 2^{\color{Orange} 2} \cdot 3^{\color{Orange} 3} \cdot 5^{\color{Orange} 1} \cdot 7^{\color{Orange} 1} \\[0.5em] 7200 &= 2^{\color{CornflowerBlue} 5} \cdot 3^{\color{CornflowerBlue} 2} \cdot 5^{\color{CornflowerBlue} 2}. \end{align*}

Die beiden Zahlen haben die gemeinsamen Primfaktoren \(2\), \(3\) und \(5\). Für den größten gemeinsamen Teiler ergibt sich entsprechend

\begin{align*} \ggT(7200, 3780) &= 2^{\color{Orange} 2} \cdot 3^{\color{CornflowerBlue} 2} \cdot 5^{\color{Orange} 1} \\[0.5em] &= 180. \end{align*}

Berechnung des größten gemeinsamen Teilers mithilfe des euklidischen Algorithmus

Hauptartikel: Euklidischer Algorithmus

Der größte gemeinsame Teiler zweier ganzer Zahlen kann alternativ mithilfe des euklidischen Algorithmus berechnet werden. Hierbei handelt es sich um die empfohlene Standardvariante zur Berechnung des ggT, da die im Allgemeinen nur aufwendig zu berechnende Primfaktorzerlegung nicht benötigt wird.

Beispiel

Es soll der größte gemeinsame Teiler von \(3780\) und \(7200\) berechnet werden. Es gilt

\begin{align*} 7200 &= 1 \cdot 3780 + 3420 \\[0.5em] 3780 &= 1 \cdot 3420 + 360 \\[0.5em] 3420 &= 9 \cdot 360 + {\color{CornflowerBlue} 180} \\[0.5em] 360 &= 2 \cdot {\color{CornflowerBlue} 180} + 0 \end{align*}

Der größte gemeinsame Teiler kann beispielsweise am Rest in der vorletzten Zeile abgelesen werden. Es gilt

\[ \ggT(7200, 3780) = 180. \]

Verallgemeinerung für mehrere Zahlen

Berechnung des größten gemeinsamen Teilers mithilfe der Primfaktorzerlegung

Die Berechnung des größten gemeinsamen Teilers kann auf mehr als zwei ganze Zahlen erweitert werden. Dies funktioniert analog zum Fall für zwei Zahlen: Es werden zunächst alle Primfaktoren ermittelt, die in jeder Zerlegung vorkommen, und diese anschließend in ihrer jeweils kleinsten vorkommenden Potenz multipliziert.

Beispiel

Es soll der größte gemeinsame Teiler von \(1200\), \(2520\) und \(3150\) berechnet werden. Es gilt

\begin{align*} 1200 &= 2^{\color{Orange} 4} \cdot 3^{\color{Orange} 1} \cdot 5^{\color{Orange} 2} \\[0.5em] 2520 &= 2^{\color{CornflowerBlue} 3} \cdot 3^{\color{CornflowerBlue} 2} \cdot 5^{\color{CornflowerBlue} 1} \cdot 7^{\color{CornflowerBlue} 1} \\[0.5em] 3150 &= 2^{\color{Magenta} 1} \cdot 3^{\color{Magenta} 2} \cdot 5^{\color{Magenta} 2} \cdot 7^{\color{Magenta} 1}. \end{align*}

Die gemeinsamen Primfaktoren sind \(2\), \(3\) und \(5\); für den größten gemeinsamen Teiler ergibt sich somit

\begin{align*} \ggT(3150, 2520, 1200) &= 2^{\color{Magenta} 1} \cdot 3^{\color{Orange} 1} \cdot 5^{\color{CornflowerBlue} 1} \\[0.5em] &= 30. \end{align*}

Berechnung mithilfe der Assoziativität

Beim größten gemeinsamen Teiler handelt es sich um eine assoziative zweistellige Verknüpfung. Es gilt

\[ \ggT\left( a, \ggT(b, c) \right) = \ggT\left( \ggT(a,b), c \right) = \ggT(a,b,c). \]

Die Assoziativität ermöglicht beispielsweise die schrittweise Berechnung des größten gemeinsamen Teilers mithilfe des euklidischen Algorithmus, so dass auch im allgemeinen Fall keine Primfaktorzerlegung benötigt wird.

Rechenregeln

Für den größten gemeinsamen Teiler gelten unter anderem die nachfolgenden Identitäten. Bei \(a,b,c \in \mathbb{Z}\) handelt es sich jeweils um ganze Zahlen; mit \(|a|\) ist der Betrag bezeichnet.

  • Der ggT ist assoziativ:
    \[ \ggT\left( a, \ggT(b, c) \right) = \ggT\left( \ggT(a,b), c \right) = \ggT(a,b,c). \]
  • Der ggT ist kommutativ:
    \[ \ggT(a,b) = \ggT(b,a). \]
  • Der ggT ist distributiv:
    \[ \ggT(a \cdot c, b \cdot c) = \ggT(a,b) \cdot |c|. \]
  • Für \(c \mid a\) und \(c \mid b\) gilt analog zur Distributivität:
    \[ \ggT(a : c, b : c) = \ggT(a,b) : |c| \]
    sowie
    \[ c \mid \ggT(a,b). \]
  • Für alle ganzen Zahlen gilt
    \begin{align*} \ggT(a,a) &= |a| \\[0.5em] \ggT(a,0) &= |a| \\[0.5em] \ggT(a,1) &= 1. \end{align*}
  • Gilt die Kongruenz \(a \equiv b \pmod{c}\), so folgt:
    \[ \ggT(a, c) = \ggT(b, c). \]
  • Darüber hinaus gelten die beiden folgenden Aussagen:
    \begin{align*} \ggT(a,b \operatorname{mod} a) &= \ggT(a,b) \\[0.5em] \ggT(a,b + ac) &= \ggT(a,b). \end{align*}

Lemma von Bézout

Das Lemma von Bézout besagt, dass sich der größte gemeinsame Teiler zweier ganzer Zahlen \(m\) und \(n\) als Linearkombination von \(m\) und \(n\) darstellen lässt, bei der nur ganzzahlige Koeffizienten auftreten.

\[ \ggT(m,n) = s \cdot m + t \cdot n \quad(\text{mit } s,t \in \mathbb{Z}) \]

Die Koeffizienten \(s\) und \(t\) können mithilfe des erweiterten euklidischen Algorithmus berechnet werden.

Anwendungen

Bruchrechnung

Beim Kürzen von rationalen Zahlen (Brüchen) wird ein gemeinsamer Faktor des Zählers und des Nenners entfernt, wobei sich der Wert des Bruchs nicht verändert. Wird der größte gemeinsame Teiler des Zählers und des Nenners gekürzt, so entsteht ein vollständig gekürzter Bruch, der nicht weiter gekürzt werden kann.

Zusammenhang mit dem kleinsten gemeinsamen Vielfachen

Für den größten gemeinsamen Teiler und das kleinste gemeinsame Vielfache zweier ganzer Zahlen gilt der folgende Zusammenhang:

\[ \ggT(a,b) \cdot \kgV(a,b) = |a \cdot b|. \]

Dies ermöglicht, das kleinste gemeinsame Vielfache auf den größten gemeinsamen Teiler zurückzuführen – und umgekehrt. Damit ist es beispielsweise möglich, das kgV (indirekt) mithilfe des euklidischen Algorithmus und somit ohne Primfaktorzerlegung zu berechnen.

\[ \kgV(a,b) = \frac{|a \cdot b|}{\ggT(a,b)} \]