ggT von 462 und 847

Frage: ggT von 462 und 847

Antwort: 77

Berechnung über die Primfaktorzerlegung
462 = 2 · 3 · 7 · 11
847 = 7 · 11 · 11 = 7 · 11²
ggT(462,847) = 7 · 11 = 77

Berechnung mit euklidischem Algorithmus
847 : 462 = 1 Rest 385
462 : 385 = 1 Rest 77
385 : 77 = 5 Rest 0
ggT(462,847) = 77