Alle Zerlegungsmöglichkeiten einer Zahl in gerade Faktoren finden.

Question

Aufgabe:

Hiho,

ich habe die Zahl 208 und möchte von dieser alle "geraden Faktorisierungen" (Zerlegungen in gerade Faktoren) finden.

Problem/Ansatz:

Bis jetzt hab ich durch "Ausprobieren" herausgefunden:

m₁ = (1 •) 208

m₂ = 2 • 104

m₃ = 4 • 52

m₄ = 8 • 26

Sind dies alle Möglichkeiten oder habe ich welche übersehen? Gibt es vielleicht eine effizientere Methode, um alle "geraden Faktorisierungen" (Zerlegungen in gerade Faktoren) von einer Zahl zu bestimmen?

Ich will diese Zerlegungsmöglichkeiten nutzen um die "Rückwärtsberechnung" für φ(n) = 204 durchführen zu können.

Freue mich über Hilfe.

Comments

Arbeite mit der Primfaktorzerlegung.

---

Ich meine durch 2 teilbar und bestehend aus 2 Faktoren.

Ich möchte dies für die Rückwärtsberechnung der Eulerschen phi-Funktion nutzen, bei der man ja im ersten Schritt versucht das Ergebnis von φ(n) (in diesem Fall φ(n) = 204) in zwei gerade Faktoren zu zerlegen und dabei alle Möglichkeiten berücksichtigen muss.

---

Also ist die eigentliche Aufgabe: "Bestimme alle natürlichen Zahlen n, für die φ(n)=208 gilt" ? 

---

Im Prinzip ja. Wollte allerdings mit möglichst wenig Hilfe, selbst auf die Lösung kommen und war nur bei der Zerlegung der Zahl in Faktoren irritiert.

---

Lobenswert. Wäre aber trotzdem hilfreich gewesen das zu wissen, um einen Kontext zu haben.

---

Ich habe meinen Fehler erkannt und nochmal im Skript nachgelesen. Mir hatte nur ein konkretes Beispiel gefehlt. Es dürfen auch Zerlegungen mit mehr als zwei Faktoren auftauchen. Danke für die Hilfe.

Answer 1

Wenn es mehr als zwei Faktoren sein dürfen :

2*4*26

usw.

Comments

War dies bei der "Rückwärtsberechnung" der Eulerschen phi-Funktion erlaubt? In unserem Skript haben wir bis jetzt nur mit Faktorisierungen bestehend aus 2 Faktoren gearbeitet. Dies irritiert mich ein wenig.

---

Wenn du nur Zerlegungen mit maximal zwei Faktoren suchst, dann sind deine Zerlegungen alle Möglichkeiten. Denn die Primfaktorzerlegung ist 208= 2⁴*13, und die ungerade 13 muss mit mindestens einer 2 "kombiniert" werden.