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.
Punkte: 11.27K
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