Euler Phi Funktionen: Berechnen sie φ(32), φ(64), φ(128); φ(27), φ(81), φ(243); φ(49); φ(25), φ(125), ...

Question

Aufgabe:

Berechnen sie φ(32), φ(64), φ(128); φ(27), φ(81), φ(243); φ(49); φ(25), φ(125), ... . Was fällt dir auf? Leite für diese und ähnliche Fälle eine allgemeine Regel ab.

Problem/Ansatz:

Ich weiß, dass wenn man die Zahlen nach ihren Primfaktoren zerlegt bei 32,64 und 128 nur 2 verwendet wird bei 27,81 und 243 das gleiche nur mit 3. Und so weiter, auch ihre Zahlen haben Ähnlichkeiten bei ihnen kommt immer die aktuelle neu dazu, φ(32) = (1,2,4,8,16,32), φ(64) = (1,2,4,8,16,32,64) usw.. Allerding weiß ich nicht wie ich daraus eine Regel machen soll.

Comments

phi(3^n) für n=0..10 ist

1, 2, 6, 18, 54, 162, 486, 1458, 4374, 13122, 39366

phi(2^n) für n=0..10 ist

1, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512

---

Ich greife mal willkürlich die Primquadrate heraus: Es ist

$$\varphi(2^2) = \varphi(4) = 2 $$ $$\varphi(3^2) = \varphi(9) = 6 $$ $$\varphi(5^2) = \varphi(25) = 20 $$ $$\varphi(7^2) = \varphi(49) = 42 $$ Die letzten beiden sind ja auch Teil der Aufgabe. Für diesen Spezialfall lässt sich leicht eine Regel finden.

Answer 1

Hallo,

ich habe mich gerade bei Wikipedia schlau gemacht.

Für Potenzen mit Primzahlen als Basis gilt demnach

\( \varphi\left(p^{k}\right)\\=p^{k}-p^{k-1}\\=p^{k-1}(p-1)\\=p^{k}\left(1-\frac{1}{p}\right) \)

Ich sehe gerade, dass du die Funktion falsch verstehst:

 φ(32) = (1,2,4,8,16,32) <-- FALSCH!

Du gibst die Teilermenge an. φ(32) gibt aber eine einzige Zahl an.

Es geht darum herauszufinden, wie viele Zahlen von 1 bis 32 den ggT 1 haben. Das sind für 32 alle ungeraden Zahlen, also 16.

φ(32)=16 ist deshalb richtig.

Für 49=7*7 sind alle Zahlen zu finden, die nicht durch 7 teilbar sind. Da es 7 Vielfache von 7 bis 49 gibt, bleiben 42 Zahlen übrig.

φ(49)=42

:-)

Comments

Sollte der Frager das nicht irgendwie selbst herausfinden?

---

Ich habe ja nur Wikipedia zitiert. Das nimmt ja nicht den Vorgang des Verstehens ab.

:-)