 |
 |
 |
 |
 |
 |
Startseite » Forum » Primzahlzerlegung von 89 (Euklidischen Algorithmus)
Primzahlzerlegung von 89 (Euklidischen Algorithmus)
Universität / Fachhochschule
Tags: Algebra
 
|
  |
|
|---|---|
|
Hi Könnte ihr mir mit dieser Aufgabe vielleicht auf die Sprünge helfen: Bestimmen Sie die Primzahlzerlegung von 89 mit dem Euklidischen Algorithmus. Dachte immer für den Euklidischen Algorithmus sind zwei Zahlenwerte notwendig ? Bin für jeden Tipp / Lösung danbar. Gruss Andi |
|
| |
anonymous 11:33 Uhr, 19.05.2006 |
|
|
Hallo die in einer Primzahlzerlegung enthaltenen "kleineren" Primzahlen können nicht größer sein als die Wurzel aus der Zahl, wenn die Zahl selbst keine Primzahl ist. Das "kleineren" bezieht sich darauf, daß es zu jeder Primzahl, die kleiner als die Wurzel aus der Zahl ist, einen Faktor geben muß, der widerum größer als die Wurzel ist. Ermittelt man den einen "kleineren" Teil, ergibt sich der andere. Würde man den "größeren" Teil ebenfalls ermitteln wollen, käme man als Faktor auf den "kleineren" und den hat man ja bereits gefunden. Im vorliegenden Beispiel können die zu untersuchenden Primzahlen also nicht größer als 9 sein. Jetzt wendet man für alle in Frage kommenden Primzahlen den Euklidischen Algorithmus an, aber zunächst für die kleinste Primzahl. Entweder ist der ggT 1 (die Primzahl ist nicht enthalten) oder er ist gleich der Primzahl, dann ist die Primzahl enthalten und man wiederholt den Algorithmus für diese Primzahl, allerdings teilt man zuvor die gegebene Zahl durch die ermittelte Primzahl. So erhält man die mehrfach enthaltenen Primzahlen. Ist eine enthaltenen Primzahl irgendwann nicht mehr enthalten, fährt man im Algorithmus mit der nächstgrößeren Primzahl fort, falls der ermittelte "Restquotient" nicht bereits 1 ist: Bsp: 89 und 2 --> ggT 1 --> 2 ist nicht enthalten 89 und 3 --> ggT 1 --> 3 ist nicht enthalten 89 und 5 --> ggT 1 --> 5 ist nicht enthalten 89 und 7 --> ggT 1 --> 7 ist nicht enthalten 89 ist Primzahl Anderes Beispiel: 6468 = (80,42...)^2 6468 und 2 --> ggT 2 --> 2 ist mindestens 1 mal enthalten 3234 und 2 --> ggT 2 --> 2 ist mindestens 2 mal enthalten 1617 und 2 --> ggT 1 --> 2 ist genau 2 mal enthalten 1617 und 3 --> ggT 3 --> 3 ist mindestens 1 mal enthalten 539 und 3 --> ggT 1 --> 3 ist genau 1 mal enthalten 539 und 5 --> ggT 1 --> 5 ist nicht enthalten 539 und 7 --> ggT 7 --> 7 ist mindestens 1 mal enthalten 77 und 7 --> ggT 7 --> 7 ist mindestens 2 mal enthalten 11 und 7 --> ggT 1 --> 7 ist genau 2 mal enthalten 11 und 11 --> ggT 11 --> 11 ist mindestens 1 mal enthalten 1 --> Primzahlzerlegung gefunden: 6468 = 2^2 * 3 * 7^2 * 11 |
|
 |
|
| Danke für die schnelle Antwort... jetzt ist es mir klarer :-) |
463922
463920