ggT von 168 und 312

Frage: ggT von 168 und 312

Antwort: 24

Berechnung über die Primfaktorzerlegung
168 = 2 · 2 · 2 · 3 · 7 = 2³ · 3 · 7
312 = 2 · 2 · 2 · 3 · 13 = 2³ · 3 · 13
ggT(168,312) = 2³ · 3 = 24

Berechnung mit euklidischem Algorithmus
312 : 168 = 1 Rest 144
168 : 144 = 1 Rest 24
144 : 24 = 6 Rest 0
ggT(168,312) = 24