Bestimmen des ggT durch Primfaktorzerlegung

Eine auch für größere Zahlen anwendbare Methode ist die Bestimmung von Primfaktoren der Zahlen, von denen der ggT gebildet werden soll.

Man zerlegt die Zahlen jeweils in ihre Primfaktoren (siehe Primfaktorzerlegung) und bestimmt anschließend alle Faktoren, die in beiden Zerlegungen auftauchen. Diese Faktoren multipliziert man anschließend.

Beispiel:

Gesucht ist ggT(8, 20)

8   = 2 · 2 · 2
20  = 2 · 2 · 5
ggT = 2 · 2   =  4 

Die blau gekennzeichneten Primfaktoren sind jene, die in beiden Zerlegungen auftauchen.

Daraus folgt: ggT(8, 20) = 4

Diese Methoden lassen sich auch für den ggT von mehr als zwei Zahlen anwenden.

Sollten die Zahlen keinen gemeinsamen Teiler besitzen (also nur die Division :1 funktioniert), verwenden wir das Wort „teilerfremd“.