ggT von 486 und 768

Frage: ggT von 486 und 768

Antwort: 6

Berechnung über die Primfaktorzerlegung
486 = 2 · 3 · 3· 3 · 3 · 3 = 2 · 3⁵
768 = 2 · 2 · 2 · 2 · 2 · 2 · 2 · 2 · 3 = 2⁸ · 3
ggT(486,768) = 2 · 3 = 6

Berechnung mit euklidischem Algorithmus
768 : 486 = 1 Rest 282
486 : 282 = 1 Rest 204
282 : 204 = 1 Rest 78
204 : 78 = 2 Rest 48
78 : 48 = 1 Rest 30
48 : 30 = 1 Rest 18
30 : 18 = 1 Rest 12
18 : 12 = 1 Rest 6
12 : 6 = 2 Rest 0
ggT(486,768) = 6