Bestimmung von Primfaktoren bei ggT / kgV ?

Question

Um den ggT und kgV von Zahlen zu bestimmen, kann man ganz einfach die Primfaktorzerlegung durchführen. Beispiel:

1. ggT(948, 225) = 3
Bestimmung durch PFZ:

948 = 4 * 225 + 48
225 = 4 * 48 + 33
48 = 1 * 33 + 15
33 = 2 * 15 + 3
15 = 5 * 3 + 0

Somit erhalten wir als ggT der beiden Zahlen die Zahl 3.
Das ist eine Variante zum Lösen mit der PFZ, eine andere Variante ist:

2. kgV(36,64)

36 = 2² * 3²
64 = 2^6
-----------------------------------
kgV(36,64) = 2^6 * 3² = 576

Nun meine Frage: Die Primfaktorzerlegung nach Variante 1 beim ggT ist mir völlig klar, nur ich weiss nicht bei Variante 2, wie ich auf den Exponenten kommen soll ? Bei 36 und 64 ist das noch relativ einfach, aber was ist, wenn ich größere Zahlen wie 484 habe ? Wie komme ich da auf die Exponenten der Primzahlen ?

bewinol · Accepted Answer

Was du da bei 1) machst, ist keine PFZ sondern der Euklidsche Algorithmus für den GGT. PFZ sähe so aus:

948 = 2*474 = 2^2*237
--> 2*2*3*79

225 = 3*75 = 3*3*25
--> 3*3*5*5

Jetzt nachschauen, welche Primzahlen in beiden Zerlegungen vorkommen, hier nur eine 3.

Nun zu deiner Schlussfrage: Da geht man schrittweise vor:

i. Zahl = Ausgangszahl
   Teiler= erste Primzahl (= 2)
ii. ist Zahl durch Teiler teilbar?
iii-ja
   Teiler notieren
   Zahl = Zahl/Teiler
   goto ii.
iII-nein
 . Teiler = nächste Primzahl
   ist Teiler = Zahl?
iv-ja
   Teiler notieren
   ENDE
iv-nein
   Teiler = nächste Primzahl
   goto ii

Beispiel 484
484 = 2*242 = 2*2*121
   = 2*2*11*11

MeMeMe · Answer

Ich versuche immer die Primfaktorzerlegung in kleinere Primfaktorzerlegungen aufzuteilen, denn die Primfaktorzerlegung von x = s * t ist ja die Primfaktorzerlegung von s * die Primfaktorzerlegung von t.

In diesem Fall sehe ich z. B. sofort, dass 484 durch 4 teilbar ist. Also weiÃ ich, dass die Primfaktorzerlegun von 484 gleich die Primfaktorzerlegung von 4 und die Primfaktorzerlegung von 484 / 4 = 121 sind. Die Primfaktorzerlegung von 4 sind offensichtlich 2 * 2 und die von 121 11 * 11. Die Primfaktorzerlegung von 484 ist also 2 * 2 * 11 * 11 und das ist 2^2 * 11^2.

Robert · Answer

Gelernt habe ich fÃ¼r kgV und ggT beides Ã¼ber die zweite Variante.

36 = 2 * 2 * 3 * 3 = 2^2 * 3^2
64 = 2 * 2 * 2 * 2 * 2 * 2 = 2^6

kgV(36, 64) = 2^6 * 3^2 = 576
ggT(36, 64) = 2^2 = 4

Die Primzahlzerlegung beginnt mit der kleinsten Primzahl (2) und wird solange dividiert bis nicht mehr teilbar ist. Dann wird mit der nÃ¤chsten Primzahl weitergemacht.

Primzahlen: 2, 3, 5, 7, 11, 13, 17, 19, usw.

Selbst fÃ¼r groÃe Zahlen wird diese Methode verwendet. Die grÃ¶Ãte Primzahl, die Ã¼berprÃ¼ft werden muss, ist kleiner als die Wurzel des Teilergebnisses.

z.B. 97 (Primzahl)
97 / 2 nicht teilbar
97 / 3 nicht teilbar
97 / 5 nicht teilbar
97 / 7 nicht teilbar

Da Wurzel(97) < 11 ist braucht man hier nicht weiterrrechnen und weiÃ dass 97 eine Primzahl ist.

###

Beispiel 2013
2013 / 3 = 671
671 / 11 = 61

2013 = 3 * 11 * 61

Beispiel 2014
2014 / 2 = 1007
1007 / 19 = 53

2014 = 2 * 19 * 53

kgV(2013, 2014) = 4.054.182
ggT(2013, 2014) = 1

Bestimmung von Primfaktoren bei ggT / kgV ?

3 Antworten