Bestimme alle n aus den natürlichen Zahlen sodass φ(n) = 1210 (Eulersche phi-Funktion)

Question

Ich komme einfach nicht dahinter wie ich diese Aufgabe lösen soll. Ich habe schon versucht von hinten nach vorne zu rechnen aber ich schaffe es einfach nicht. Außerdem hab ich schon unzählige Foren durchforstet und bin noch auf nichts gestoßen.

Kann mir wer helfen?

Bestimme alle n aus den natürlichen Zahlen sodass φ(n) = 1210 (Eulersche phi-Funktion ?)

GLG

Answer 1

Ich habe

$$ 1210 = 11^2 \cdot 10 = 11^3 \cdot \left(1-\dfrac{1}{11} \right) = \varphi\left(11^3\right) $$

(Das ist aber nicht die einzige Lösung!)

Comments

super danke! Aber wie komm ich dann eigentlich auf alle Lösungen? muss ich da durchprobieren?

---

Na, viel mehr wird es nicht geben und 2 ist teilerfremd zu 11 und die einzige von 1 verschiedene Zahl mit \(\varphi(2)=1\).

---

Was passiert aber wenn man z.B. sagt φ(n) = p_prim ?

Dann kann ich ja nicht auf den ersten Blick die Lösung für n finden. Da muss es ja eine Struktur geben um dies auszurechnen oder? Weil da würd ich dann schon wieder anstehen, obwohl das nur ein ähnliches Beispiel ist.

Wie würde man dann an sowas rangehen?

Answer 2

EulerPhi[n^k] = EulerPhi[n] n^{k - 1}

EulerPhi[n^k]/n^{k - 1} = EulerPhi[n] =1210=2*5*11²

Prime(x)^{k-1}*(Prime(x)-1)=1210 -> k=3, x=5 und Prime(5)=11

Lösungen:

±1331=11³

±2662=2*11³

bis 100000 keine weiteren Lösungen...

Anderer Weg:

EulerPhi[n] EulerPhi[m] = (EulerPhi[m n] EulerPhi[ggT[n, m]])/ggT[n, m]

... reicht für heute...