Zeigen Sie Eulersche ϕ Funktion

Question

Aufgabe:

Betrachten Sie die Eulersche ϕ-Funktion, welche fur nat ¨ urliche Zahlen ¨ n ∈ N definiert ist als Anzahl der zu n teilerfremden naturlichen Zahlen kleiner gleich ¨ n, d.h. ϕ(n) = |{a ∈ N | a ≤ n und ggT(a, n) = 1}|.
(a) Bestimmen Sie alle n ∈ N, so dass ϕ(n) ungerade ist.
(b) Bestimmen Sie alle n ∈ N, so dass ϕ(n) = ϕ(2n) gilt.
(c) Bestimmen Sie alle n ∈ N, so dass ϕ(n) = 42 gilt.

Problem/Ansatz:

Können Sie mir helfen, bitte diese drei Fragen

Answer 1

Berechne mal ein paar Beispiele und beachte die Bedingung a≤n.

ϕ(1)=1  denn wenn ggT(a,1)=1 gelten soll, kann nur a=1 sein.

ϕ(2)=1  denn wenn ggT(a,1)=1 gelten soll, kann nur a=1 sein, denn ggT(2,2)=2.

ϕ(3)=2  denn wenn ggT(a,1)=1 gelten soll, kann  a=1 oder a=2 sein.

ϕ(4)=2  denn wenn ggT(a,1)=1 gelten soll, kann a=1 oder a=3 sein.

ϕ(5)=4  denn wenn ggT(a,1)=1 gelten soll, kann a=1 ,2,3 oder 4 sein.

Hier merkt man vielleicht schon: Bei allen ungeraden Primzahlen ist

immer ϕ(p)=p-1 , also eine gerade Zahl.

Vielleicht hilft das ja schon was. Mehr z.B. auch hier:

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

Answer 2

Aus dem chinesischen Restsatz ergibt sich, dass \(\varphi\)

eine sogenannte multiplikative zahlentheoretische Funktion ist,

d.h. für teilerfremde \(m,n\) gilt \(\varphi(mn)=\varphi(m)\varphi(n)\).

Damit können wir (b) untersuchen:

Ist \(n\) ungerade, dann folgt \(\varphi(2n)=\varphi(2)\varphi(n)\), also

wegen \(\varphi(2)=1\) ist dann \(\varphi(n)=\varphi(2n)\).

Ist hingegen \(n\) gerade, so ist \(n=2^rm\) mit ungeradem \(m\) und \(r\geq 1\).

Hier haben wir

\(\varphi(n)=\varphi(2^r)\varphi(m)=2^{r-1}\varphi(m)\)

und

\(\varphi(2n)=\varphi(2^{r+1})\varphi(m)=2^r\varphi(m)\) ,

also \(\varphi(n)\neq \varphi(2n)\)