Hilfe beim Beweis-Ansatz

Aufrufe: 649     Aktiv: 15.05.2021 um 16:39

0
Hi, ich muss beweise, dass es zu jedem m ∈ N nur endlich viele n ∈ N gibt, sodaß ϕ(n) = ϕ(m) ist.

Irgendeinen Tipp, wie ich da anfangen soll? Ich hab ein bisschen herumprobiert mit verschieden Schreibweisen von ϕ(n) als Produkt von Primzahlen, relativ prim zu m oder eben nicht, aber irgendwie stehe ich gerade auf der Leitung... Irgendeinen Tipp zum Anfangen wäre toll :) 

Danke schon mal :)

lg Lola
Diese Frage melden
gefragt

Punkte: 20

 
Kommentar schreiben
1 Antwort
1
Um es etwas einfacher zu machen, zeigen wir lieber: Für alle \(m\in\mathbb N\) gibt es nur endlich viele \(n\in\mathbb N\) mit \(\varphi(n)=m\). Das ist natürlich äquivalent zu deiner Behauptung.
Sei \(n\in\mathbb N\) mit \(\varphi(n)=m\). Sei \(p\) ein Primfaktor von \(n\) und \(k\) die \(p\)-Potenz von \(n\), also \(p^k|n\) und \(p^{k+1}\nmid n\). Dann gilt \(p-1|\varphi(n)\) und \(p^{k-1}|\varphi(n)\). Insbesondere gilt also \(p-1\leq\varphi(n),p^{k-1}\leq\varphi(n)\) für jeden Primfaktor von \(p\).
Jetzt überleg dir, wie groß \(n\) maximal sein kann. Hat \(n\) zu viele Primfaktoren, dann wird \(p-1\) größer als \(\varphi(n)\), werden die Exponenten der Primfaktoren zu groß, wird \(p^{k-1}\) größer als \(\varphi(n)\).

Das ist die Beweisidee, jetzt musst du das ganze nur noch formalisieren.
Diese Antwort melden
geantwortet

Punkte: 11.27K

 

Super, danke! Ich versuchs gleich umzusetzen - dumme frage: wieso ist das äquivalent: φ(n)=m ?   ─   pfeiferl99 15.05.2021 um 15:45

1
Deine Behauptung ist \(\forall m\in\mathbb N\) existieren nur endlich viele \(n\in\mathbb N\) mit \(\varphi(n)=\varphi(m)\).
Meine Behauptung ist \(\forall m\in\mathbb N\) existieren nur endlich viele \(n\in\mathbb N\) mit \(\varphi(n)=m\).
Die zweite Behauptung impliziert offensichtlich die erste (ersetze \(m\) mit \(\varphi(m)\)), die zweite impliziert auch die erste (offensichtlich für alle \(m\in\varphi(\mathbb N)\) und für alle anderen \(m\) gibt es überhaupt keine passenden \(n\), und 0 ist sicher endlich.)
Also sind die beiden Behauptungen äquivalent.
  ─   stal 15.05.2021 um 16:39

Kommentar schreiben