Zeigen Sie: Es gibt keine natürliche Zahl n , so dass φ ( n ) = 194 ist

Question

Aufgabe:

Sei φ  : ℕ→ℕ die Eulersche φ-Funktion.

Zeigen Sie:  Es gibt keine natürliche Zahl n , so dass φ ( n ) = 194 ist

Problem/Ansatz:

Answer 1

Für eine Primzahl \(p\) gilt \(\varphi(p) = p-1\). Wenn also \(n\) in \(\varphi(n)=194\) eine Primzahl wäre, so müsste \(n=195\) sein. Das ist aber nicht der Fall, da \(195\) durch \(5\) teilbar ist. Somit muss es mindestens zwei teilerfremde Zahlen \(x\) und \(y\) geben, für die gilt: $$n = x \cdot y, \space \gcd( x, y) = 1 \quad \implies \varphi(n=x \cdot y) = \varphi(x) \cdot \varphi(y)$$ nun ist aber \(194 = 2\cdot 97\) die Primzahlzerlegung von \(194\) und es existiert keine Zahl deren Phi-Funktion ungerade und \(>1\) ist. Dies folgt aus der allgemeinen Berechnungsformel für die Phi-Funktion.

Folglich existiert keine Zahl \(n \in \mathbb{N}\) für die \(\varphi(n)=194\) gilt.

Comments

Wieso muss es dann zwei Teilerfremde Teiler x und y geben? Wäre es nicht möglich, dass n die Potenz einer Primzahl ist? Diesen Fall müsste man doch noch ausschließen oder?

---

Wieso muss es dann zwei Teilerfremde Teiler x und y geben? Wäre es nicht möglich, dass n die Potenz einer Primzahl ist?

Die Potenz 'hoch 1' hatte ich ja bereits ausgeschlossen (s.Antwort) und für eine höhere Potenz muss \(\varphi(n)\) selbst Teiler von \(n\) sein. Das heißt aber auch, dass \(\varphi(n)\) zwei Teiler besitzt, die sich um 1 unterscheiden.

Ok - das muss man noch ausschließen. Hatte ich vielleicht damals auch implizit getan.

---

Ich verstehe nicht so ganz, wieso φ(n) (für den Fall, dass n die Darstellung p^d mit d>1) die Zahl n teilen soll.

Beispiel: n = 5*5 :

φ(25) ist auf jeden Fall eine gerade natürliche Zahl, diese wird nicht 25 teilen.

Vielleicht habe ich dich auch nur falsch verstanden. Es wäre nett, wenn du mir das nochmal erklären könntest.

---

Ich verstehe nicht so ganz, wieso φ(n) (für den Fall, dass n die Darstellung pd mit d>1) die Zahl n teilen soll.

Beispiel: n = 5*5 :

φ(25) ist auf jeden Fall eine gerade natürliche Zahl, diese wird nicht 25 teilen.

Nein - nicht 25, aber 5. Die Phi-Funktion ergibt sich aus$$\varphi(n) = \prod_{p\mid n} p^{k_p-1}(p-1)$$Im Falle von \(25=5^2\) ist \(p=5\) und \(k_p=2\) ... also$$\varphi(25) = 5^{2-1}(5-1) = 20$$Mit \(p=5\) und \(k_p \gt 1\) enthält \(\varphi(25)\) die Teiler \(p\) und \(p-1\), hier 5 und 4.

Sei \(n\) eine Primzahlpotenz mit \(k_p\gt1\), und \(p \in \mathbb P\backslash2\), so muss \(\varphi(n)\) zwei Teiler \(p\) und \(p-1 \gt 1\) enthalten. Und den Fall \(p=2\) kann man bei \(194=2\cdot 97\) auch schnell ausschließen.

---

Danke für die ausführliche Erklärung, jetzt versteh ich es. :)

LG