Der größte gemeinsame Teiler (ggT) zweier natürlicher Zahlen
anhand eines Beispiels:
Welche Zahl ist der größte gemeinsame Teiler von 36 und 120?
Ein gemeinsamer Teiler ist 3 (denn 3 teilt 36 und 120), ein weiterer
gemeinsamer Teiler ist 6, und wieder ein anderer ist 12.
Ist 12 der größte gemeinsame Teiler oder gibt es einen noch
größeren?
Eine definitive Antwort auf diese Frage liefert die
Primfaktorzerlegung der beiden gegebenen Zahlen:
Der ggT ist das Produkt aller gemeinsam
auftretenden Primfaktoren, wobei jeder Faktor nur so oft genommen wird,
wie er höchstens in beiden Zahlen auftritt.
(Mit anderen Worten: es muß immer die kleinere
Hochzahl genommen werden).
In unserem Beispiel heißt das:
Die 2 tritt in 36 zweimal auf, in 120 dreimal, also ist 22
ein Teiler beider Zahlen (während 23 nur Teiler von 120 ist).
Die 3
tritt in beiden Zahlen auf (während 32 nur 36 teilt,
nicht aber 120),
und die 5 tritt nur in 120 auf, nicht aber in 36. Der ggT
von 36 und 120 ist daher
In analoger Weise kann der ggT von mehr als zwei natürlichen Zahlen ermittelt
werden.