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
Eine Formel für den ggT ergibt sich aus der kanonischen Primfaktorzerlegung der gegebenen Zahlen
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
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.
Schreiben Sie uns!