Finding Greatest Common Divisor (GCD) with Primality Decomposition and Euclidean Algorithm
Die Aufgabe besteht darin, den größten gemeinsamen Teiler (ggT) für drei Paare von Zahlen zu finden, einmal mit Hilfe der Primfaktorzerlegung und einmal mit dem euklidischen Algorithmus.
Lassen Sie uns die Berechnung für jedes Paar durchführen:
a) ggT(866, 78)
**Primfaktorzerlegung:**
- 866 = 2 x 433
- 78 = 2 x 3 x 13
Der einzige gemeinsame Faktor ist 2, folglich ist der ggT(866, 78) = 2.
**Euklidischer Algorithmus:**
- 866 = 78 x 11 + 8
- 78 = 8 x 9 + 6
- 8 = 6 x 1 + 2
- 6 = 2 x 3 + 0
Hier können wir sehen, dass der Rest Null wird, wenn wir 6 durch 2 teilen. Daher ist der ggT(866, 78) = 2.
b) ggT(1197, 1449)
**Primfaktorzerlegung:**
- 1197 = 3 x 3 x 7 x 19
- 1449 = 3 x 13 x 37
Beide Zahlen haben die Primzahl 3 als gemeinsamen Faktor. Da 3 zweimal in 1197 vorkommt, aber nur einmal in 1449, ist der ggT(1197, 1449) = 3.
**Euklidischer Algorithmus:**
- 1449 = 1197 x 1 + 252
- 1197 = 252 x 4 + 189
- 252 = 189 x 1 + 63
- 189 = 63 x 3 + 0
Der Rest wird 0, wenn wir 189 durch 63 teilen, also ist der ggT(1197, 1449) = 63.
c) ggT(2061, 4910)
**Primfaktorzerlegung:**
- 2061 = 3 x 3 x 229
- 4910 = 2 x 5 x 491
Es gibt hier keine gemeinsamen Primfaktoren, daher ist der ggT(2061, 4910) = 1.
**Euklidischer Algorithmus:**
- 4910 = 2061 x 2 + 788
- 2061 = 788 x 2 + 485
- 788 = 485 x 1 + 303
- 485 = 303 x 1 + 182
- 303 = 182 x 1 + 121
- 182 = 121 x 1 + 61
- 121 = 61 x 1 + 60
- 61 = 60 x 1 + 1
- 60 = 1 x 60 + 0
Da der Rest Null wird, wenn wir 60 durch 1 teilen, ist der ggT(2061, 4910) = 1.
