Größter gemeinsamer Teiler

Größter gemeinsamer Teiler

Der größte gemeinsamer Teiler, kurz ggT, ist die größte natürliche Zahl bezüglich Teilbarkeit, 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).

Beispiele sind: ggT(12,18)=6, ggT(100,20)=20, ggT(-4,14)=2, ggT(3,8)=1, ggT(5,0)=5 sowie (per Definition) ggT(0,0)=0

Berechnet wird der ggT durch Primfaktorzerlegung oder mittels des Euklidischen Algorithmus.

Nach dem Satz von Bézout lässt sich der ggT(a,b) als Linearkombination von a und b mit zwei ganzen Zahlen i, j darstellen, also:

Die Faktoren i und j können mit einer Erweiterung des Euklidischen Algorithmus bestimmt werden. Nützlich ist dies z.B. bei der Berechnung von Inversen in Restklassenringen.

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

Siehe auch: kgV und ggT