Primfaktorzerlegung von ϕ(2^a · 3^b · 5^c · 7^d · 11^e · 13^f · 17^g · 19^h )

Question

Wie geht man so etwas an? Wenn mir das jemand anhand dieser Aufgabe zeigen könnte wäre ich ihm dankbar!

Comments

Hast du irgendwelche Angaben zu diesen phi ?

---

Ja, das soll die eulersche phi Funktion sein. Komme aber trotz Wikipedia und Skript nicht dahinter wie sie richtig funktioniert...speziell in diesem Fall

---

Schon da steht alles, was man für diese Aufgabe wissen muss:

https://de.wikipedia.org/wiki/Eulersche_Phi-Funktion

Siehe die Abschnitte "Multiplikative Funktion" und "Potenz von Primzahlen". Billiger geht es eigentlich kaum.

Answer 1

Nur 2 Gesetze von EulerPhi(x) anwenden

http://www.lamprechts.de/gerd/php/RechnerMitUmkehrfunktion.php

§1: EulerPhi(a*b) = EulerPhi(a) * EulerPhi(b)

§2: Phi(Prime(x)^k) = Prime(x)^{k-1}*(Prime(x)-1)=Prime(x)^k*(1-1/Prime(x))

Prime(x) ist die Primzahlenfunktion: Prime(1)=2, Prime(2)=3, ...

also in Deinener Aufgabe x=1...8

Beispiel: Phi(Prime(4)^3)=Phi(7^3)=Phi(343)

= 7^{3-1}*(7-1)=7²*6=294