ggT aus Primfaktoren

Das Auflisten der Faktoren wird bei größeren Zahlen langsam, und Primfaktorzerlegungen sind schneller. Zerlege beide Zahlen in Faktoren: 45 ist 3 × 3 × 5 und 75 ist 3 × 5 × 5. Die gemeinsamen Primzahlen sind eine 3 und eine 5.

Multipliziere die gemeinsamen Primzahlen: 3 × 5 ist 15, der GGT von 45 und 75. Eine Primzahl zählt nur so oft als gemeinsam, wie sie in beiden Zahlen vorkommt: 45 hat zwei 3en, aber 75 hat nur eine, also kommt nur eine 3 hinein.

Warum es funktioniert: Ein gemeinsamer Faktor kann nur aus Primzahlen gebildet werden, die beide Zahlen enthalten. Nimmt man jede gemeinsame Primzahl so oft, wie es bei beiden möglich ist, erhält man den größten gemeinsamen Faktor. Bei Exponenten nimmt man jede gemeinsame Primzahl mit dem kleineren Exponenten: 3^2 × 5 und 3 × 5^2 ergeben 3 × 5.