Größter gemeinsamer Teiler

Der größte gemeinsamer Teiler, kurz ggT, ist die größte natürliche Zahl, die zwei oder mehrere ganze Zahlen ohne Rest teilt. Den größten gemeinsamen Teiler der Zahlen a und b schreibt man als ggT(a,b) oder wenn keine Verwechslungen zu befürchten sind auch als (a,b). Ist er größte gemeinsame Teiler zweier Zahlen 1, so nennt man diese Zahlen teilerfremd.

Beispiele sind:

• ggT(12, 18) = 6
• ggT(100, 20) = 20
• ggT(-4, 14) = 2
• ggT(3, 8) = 1
• ggT(5, 0) = 5
• ggt(0, 0) = 0 (per Definition)

Oftmals wird die 0 als Argument verboten.

Berechnet wird der ggT durch Primfaktorzerlegung, mit dem euklidischen Algorithmus oder dem Algorithmus nach Stein (Wobei die Methode durch Primfaktorzerlegung in der Praxis meist nicht verwendet wird, weil sie deutlich langsamer ist - in der Tat verwenden moderne Algorithmen zur Primfaktorzerlegung den ggT mittels Euklidischen Algorithmus um die Primfaktoren zu bestimmen).

Die Bestimmung des ggT ist von zentraler Bedeutung in der angewandten Zahlentheorie, so bei kryptographischen Verfahren, wie dem RSA-Algorithmus.

Der ggT von a und b lässt sich als Linearkombination von a und b mit zwei ganzen Zahlen s, t darstellen: ggT(a,b)=sa+tb. Die Koeffizienten s und t können mit einer Erweiterung des Euklidischen Algorithmus bestimmt werden. Nützlich ist dies z. B. bei der Berechnung von Inversen in Restklassenringen.

Beispiele sind:

• ggT(12,18) = 6 = (-1)·12 + 1·18
• ggT(3,8) = 1 = (-5)·3 + 2·8

Rechenregeln

Für alle ganzen Zahlen a, b gilt:

• ggT(a,b) = ggT(b,a)
• ggT(-a,b) = ggT (a,b)
• ggT(a,0) = a

Verallgemeinerung auf beliebige kommutative Ringe

Um den Begriff des größten gemeinsamen Teilers auf beliebige kommutative Ringe ausdehnen zu können, muss man die Definition etwas ändern, da in beliebigen Ringen nicht vorausgesetzt werden kann, dass die Elemente bezüglich "<" angeordnet werden können. Deshalb ersetzt man diese Anordnung durch die durch den Teilbarkeitsbegriff definierte partielle Ordnung.

Eine Zahl d heißt größter gemeinsamer Teiler zweier Zahlen a und b, wenn d|a und d|b und für jede Zahl d', für die gilt d'|a und d'|b gilt d'|d.

Beispiel im Gaußschen Zahlenring Z+iZ ist der größte gemeinsame Teiler von 2 und 1+3i gerade 1+i, denn 2=-i(1+i)² und 1+3i=(1+i)(2+i). Genau genommen ist 1+i ein größter gemeinsamer Teiler, da alle zu dieser Zahl assozierten Zahlen ebenfalls größte gemeinsame Teiler sind.

Auch diese allgemeinere Definition lässt sich ganz natürlich auf mehrere Zahlen ausweiten (sogar auf unendlich viele).

Das ggT lässt sich mit dem Euklidischen Alrorithmus bestimmen.

Siehe auch: kgV und ggT