Eulerfunktion < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 14:06 Sa 26.11.2011 | | Autor: | Jim |
| Aufgabe | Beweis der Eigenschaften der Eulerfunktion phi
1. phi(n) -> [mm] \infty [/mm] für n -> [mm] \infty
[/mm]
2. lim sup phi(n)/n = 1 und lim inf phi(n)/n = 0 |
Hallo,
also ich habe mich mit der Eulerfunktion beschäftigt und finde die beiden Aussagen auch logisch. Nur der Beweis will mir nich gelingen. Mein Problem ist, dass die Eulerfunktion phi keine wirkliche Formel ist, die ich dann einfach gegen unendlich lassen laufen könnte.
Auch zu der 2ten Eigenschaft habe ich mir das nur mit Beispielen verdeutlicht, aber ich denke, dass dies für einen Beweis natürlich nicht reicht.
Ich wäre für einen Ansatz wirklich dankbar.
Gruß Jim
Ich habe dies Frage in keinem anderem Forum gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 14:41 Sa 26.11.2011 | | Autor: | felixf |
Moin Jim!
> Beweis der Eigenschaften der Eulerfunktion phi
>
> 1. phi(n) -> [mm]\infty[/mm] für n -> [mm]\infty[/mm]
>
> 2. lim sup phi(n)/n = 1 und lim inf phi(n)/n = 0
> Hallo,
>
> also ich habe mich mit der Eulerfunktion beschäftigt und
> finde die beiden Aussagen auch logisch. Nur der Beweis will
> mir nich gelingen. Mein Problem ist, dass die Eulerfunktion
> phi keine wirkliche Formel ist, die ich dann einfach gegen
> unendlich lassen laufen könnte.
Kennst du die Darstellung [mm] $\phi(n) [/mm] = n [mm] \cdot \prod_{p \mid n} \frac{p - 1}{p}$? [/mm] Die koennte hier nuetzlich sein. (Spaetestens beim zweiten Teil.)
Dazu ein Tipp: ist $n = [mm] \prod_{i=1}^k p_i^{e_i}$ [/mm] eine Primfaktorzerlegung von $n$, so gilt $k [mm] \le \log_2 [/mm] n$. Verwende dies, um [mm] $\phi(n)$ [/mm] durch einen Ausdruck in $n$ und [mm] $\log_2 [/mm] n$ nach unten abzuschaetzen.
> Auch zu der 2ten Eigenschaft habe ich mir das nur mit
> Beispielen verdeutlicht, aber ich denke, dass dies für
> einen Beweis natürlich nicht reicht.
Es ist klar, dass $0 [mm] \le \phi(n) \le [/mm] n$ gilt. Damit folgt $0 [mm] \le \liminf \phi(n)/n \le \limsup \phi(n)/n \le [/mm] 1$.
Fuer [mm] $\limsup \phi(n)/n [/mm] = 1$ musst du eine unendliche Folge von Zahlen [mm] $(n_k)_{k\in\IN}$ [/mm] finden, fuer die [mm] $\phi(n_k)/n_k \to [/mm] 1$ gilt. Dazu muss [mm] $\phi(n_k)$ [/mm] moeglichst gross sein. Hast du eine Idee, was fuer Zahlen du verwenden koenntest?
Fuer [mm] $\liminf \phi(n)/n [/mm] = 0$ brauchst du eine Folge von Zahlen [mm] $(n_k)_{k\in\IN}$, [/mm] so dass [mm] $\phi(n_k)$ [/mm] jeweils moeglichst klein ist. Die obige Darstellung von [mm] $\phi$ [/mm] gibt dir vielleicht eine Idee: je mehr dieser Faktoren [mm] $\frac{p - 1}{p}$ [/mm] vorhanden sind, desto kleiner ist [mm] $\phi(n)/n$.
[/mm]
LG Felix
|
|
|
|
