Größten gemeinsamen Teiler bestimmen. Vorgehensweise? ggT(a; b) von a = 38304 und b = 2464

Question

hallo ihr lieben,

Ich bräuchte mal eben etwas Hilfe zu meiner Aufgabe. Ich soll den größten gemeinsamen Teiler finden, nur wie genau gehe ich da vor?

genauer gesagt von  ggT(a; b) von a = 38304 und b = 2464, sowie von a = 104856 und b = 29580.

Vielen Dank schonmal! :)

Answer 1

Üblicherweise bestimmt man zunächst die Primfaktorzerlegungen der gegebenen Zahlen:

38304 = 2 * 2 * 2 * 2 * 2 * 3 * 3 * 7 * 19 = 2 ⁵ * 3 ² * 7 * 19

2464 = 2 * 2 * 2 * 2 * 2 * 7 * 11 = 2 ⁵ * 7 * 11 

Der ggT ist dann das Produkt aus allen Primfaktoren, die in beiden Zerlegungen auftreten und zwar in der höchsten in beiden Zerlegungen auftretenden Potenz, hier also:

ggT ( 38304 , 2464 ) = 2 ⁵ * 7 = 224

 

Eine andere Methode bestimmt den ggT zweier Zahlen eher algorithmisch:

Der ggT zweier Zahlen a und b ist gleich dem ggT der kleineren dieser Zahlen und der Differenz der beiden Zahlen:

Am Beispiel:

ggT ( 38304 , 2464 )

= ggT ( 2464 , 35840 )

= ggT ( 2464 , 33376 )

= ggT ( 2464 , 30912 )

...

= ggT ( 2464 , 3808 )

= ggT ( 2464 , 1344 )

= ggT ( 1344 , 1120 )

= ggT ( 1120 , 224 )

= ggT ( 224 , 896 )

= ggT ( 224 , 672 )

= ggT ( 224 , 448 )

= ggT ( 224 , 224 )

Sobald beide Zahlen gleich sind, sind sie gleich dem ggT der ursprünglichen Zahlen. 

Comments

vielen dank!! wirklich sehr lieb von dir : )

noch eine letzte kleine frage bezüglich der aufgabe;


wie gehe ich vor, wenn ich die  ggT  in der Form d = sa + tb darstellen soll? ich komme irgendwie nicht auf den lösungsweg..der wird mir bestimmt ersichtlich, wenn ich die lösung vor mir habe -.-

---

Hmm, was sollen denn s, a, b und t sein?
Welche Eigenschaften sollen diese Variablen / Parameter haben?

---

Das ist aus der Aufgabe leider nicht ersichtlich. Es steht nur das da,was ich geschrieben habe.

---

Nun, dann kann ich leider nicht helfen.
Man kann jede Zahl als Summe zweier Zahlen schreiben und wenn man es geschickt anstellt, dann kann man auch jede Zahl als Summe zweier Produkte schreiben.

224 etwa kann man z.B. schreiben als:

100 + 124

und das wiederum als:

4 * 25 + 2 * 64

---

Bei a=38304 b=2464 musst du die Zeilen verwenden, bei denen du den ggT berechnet hast.

1344 = 1*1120 + 224

umstellen nach

224 = 1344 -1120

Nun kannst du 1120 durch 2464 - 1344 ersetzen (siehe ggT berechnung).

Und dann immer so weiter.

Am Ende sollte 224 = 2*38304 - 31*2464 rauskommen

-> s = 2 und t = -31

Answer 2

Hallo , alle teilermengen der beiden Zahlen bestimmen und dann den größten gemeinsamen Teilet heraus fischen , oder aber mit dem Euklidschen Algorithmus.

im ersten Fall ist der  ggt  224

im zweiten Fall  ist der ggt 204