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.
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
Link
geantwortet
stal
Punkte: 11.27K
Punkte: 11.27K
Super, danke! Ich versuchs gleich umzusetzen - dumme frage: wieso ist das äquivalent: φ(n)=m ?
─
pfeiferl99
15.05.2021 um 15:45
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
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