Größere Schriftzeichen   

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:
36
=
22 ×32
(1)
120
=
23 × 3 × 5
(2)
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
22 × 3 = 12.
(3)

In analoger Weise kann der ggT von mehr als zwei natürlichen Zahlen ermittelt werden.