0 Daumen
493 Aufrufe

Aufgabe:

Sei φ \varphi Eulers Funktion. Bestimmen sie alle Zahlen n n , so dass φ(n)=1000 \varphi(n)=1000 gilt.


Problem/Ansatz:

Moin, wie Löse ich diese Aufgabe? Weiß das es was mit Kongruenzen zu tun hat, aber wie wende ich das an, um eine Lösung zu erhalten?

Avatar von

1 Antwort

0 Daumen
 
Beste Antwort

für teilerfremde x,yx,y gilt φ(xy)=φ(x)φ(y)\varphi(xy)=\varphi(x)\varphi(y)

und für eine Primzahl pp gilt φ(pk)=pkpk1=pk1(p1)\varphi(p^k)=p^k-p^{k-1}=p^{k-1}(p-1).

Mit diesen Formeln bin ich auf φ(2500)=1000\varphi(2500)=1000 gekommen.

Avatar von 29 k

Ah ok, ja die Formel hab ich auch schon im Internet gefunden, aber viel zu kompliziert gedacht xD
Vielen Dank, das hilft weiter^^

Ein anderes Problem?

Stell deine Frage