Direkt zum Inhalt

Lexikon der Mathematik: größter gemeinsamer Teiler

ggT, derjenige positive gemeinsame Teiler ganzer Zahlen n1, …, nk ∈ ℤ \{0}, der von jedem anderen gemeinsamen Teiler dieser Zahlen geteilt wird. Man benutzt die Bezeichnungen \begin{eqnarray}(n1,\mathrm{\ldots },{n}_{k})=\text{ggT}\,({n}_{1},\mathrm{\ldots },{n}_{k})\\ \,=\,\gcd \,({n}_{1},\mathrm{\ldots },{n}_{k});\end{eqnarray} die letztere findet sich in englischsprachigen Texten und steht für „greatest common divisor“.

Eine Formel für den ggT ergibt sich aus der kanonischen Primfaktorzerlegung der gegebenen Zahlen \begin{eqnarray}{n}_{j}=\pm \,\displaystyle \prod _{p}{p}^{{\nu }_{p}\,({n}_{j})},\end{eqnarray} mit Vielfachheiten νp(nj) ≥ 0. Dann gilt \begin{eqnarray}\text{ggT}\,({n}_{1},\mathrm{\ldots },{n}_{k})=\displaystyle \prod _{p}{p}^{\min \,\{{\nu }_{p}\,({n}_{1}),\mathrm{\ldots },\,{\nu }_{p}\,({n}_{k})\}}.\end{eqnarray}

Auch ohne Primfaktorenzerlegung läßt sich der ggT sehr effizient mit dem Euklidischen Algorithmus ermitteln: Man berechnet zunächst den ggT von zwei Zahlen n1, n2 und geht dann induktiv weiter unter Benutzung der Formel \begin{eqnarray}({n}_{1},\mathrm{\ldots },{n}_{k})=(({n}_{1},\mathrm{\ldots },{n}_{k\,-\,1}),\,{n}_{k});\end{eqnarray} so muß immer nur der ggT von zwei Zahlen berechnet werden.

Der Begriff des größten gemeinsamen Teilers läßt sich auf auch allgemeinere algebraische Strukturen als Z übertragen (größter gemeinsamer Teiler von Polynomen), beispielsweise sind die idealen Zahlen hierdurch motiviert.

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos