Aufgabe:
Sei φ \varphi φ Eulers Funktion. Bestimmen sie alle Zahlen n n n, so dass φ(n)=1000 \varphi(n)=1000 φ(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?
für teilerfremde x,yx,yx,y gilt φ(xy)=φ(x)φ(y)\varphi(xy)=\varphi(x)\varphi(y)φ(xy)=φ(x)φ(y)
und für eine Primzahl ppp gilt φ(pk)=pk−pk−1=pk−1(p−1)\varphi(p^k)=p^k-p^{k-1}=p^{k-1}(p-1)φ(pk)=pk−pk−1=pk−1(p−1).
Mit diesen Formeln bin ich auf φ(2500)=1000\varphi(2500)=1000φ(2500)=1000 gekommen.
Ah ok, ja die Formel hab ich auch schon im Internet gefunden, aber viel zu kompliziert gedacht xDVielen Dank, das hilft weiter^^
Ein anderes Problem?
Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos