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. 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 zweier ganzer Zahlen i, j darstellen, also:

ggT(a,b) = i·a + j·b 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 endlichen multiplikativen Gruppen. siehe auch: kgV und ggT