Abschätzung von \phi(n) < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 20:51 Do 26.04.2007 | | Autor: | securido |
| Aufgabe | Zeige dass für hinreichend grosse natürliche Zahlen n gilt
[mm] \phi(n) [/mm] > n / log n
wobei [mm] \phi(n) [/mm] die Eulersche Phi-Funktion bezeichnet, also die Anzahl der natürlichen Zahlen 1 <= a < n mit ggT(a,n)=1. |
Hallo,
ich möchte zeigen dass für hinreichend grosse n die Ungleichung
[mm] \phi(n) [/mm] > n / log n
gilt. Das Ganze sieht verdächtig nach dem Primzahlsatz aus, und ich habe auf Wolfram.com die Ungleichung [mm] \pi(n) [/mm] < [mm] \phi(n) [/mm] gefunden, wobei [mm] \pi(n) [/mm] die Anzahl der Primzahlen kleiner als n angibt. Aber ich kann keinen Beweis finden. Kann mir jemand dabei helfen?
Nebenbei bemerkt, das ist keine Haus-/übungsaufgabe, daher sind auch vollständige Lösungen oder Verweise darauf willkommen. Man lernt ja auch daraus sich fremde Beweise anzusehen 
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 09:56 Mo 30.04.2007 | | Autor: | securido |
Hallo wauwau,
vielen Dank für Deine Antwort. Habe das pdf grade mal kurz überflogen und es sieht vielversprechend aus.
Bislang habe ich es "provisorisch" mal so begründet:
Nach dem Primzahlsatz gilt
[mm] \pi(n) [/mm] ~ n / [mm] \ln [/mm] n
wobei ~ asymtotische Gleichheit bezeichnet. Ausserdem gilt nach http://functions.wolfram.com/13.06.29.0012.01 dass [mm] \phi(n) [/mm] > [mm] \pi(n) [/mm] gilt für alle n [mm] \geq [/mm] 91.
Wenn man dann noch [mm] \log [/mm] als denn 2er Logarithmus definiert dann hat man
[mm] \frac{\phi(n)}{n} [/mm] < [mm] \frac{\pi(n)}{n} [/mm] ~ [mm] \frac{1}{\ln n} [/mm] = [mm] \frac{\log e}{\log n} [/mm] < [mm] \frac{1}{\log n}
[/mm]
für hinreichend grosse n > [mm] n_0, [/mm] weil [mm] \log_2 [/mm] e > 1.4.
Ich finde es allerdings sehr unbefriedigend nicht zu wissen woher die Ungleichung [mm] \phi(n) [/mm] > [mm] \pi(n) [/mm] kommt...
Was ist von obigem Argument zu halten?
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 11:02 Mo 30.04.2007 | | Autor: | wauwau |
Überprüfe noch mal deine größer, kleiner Zeichen..... da ist was durcheinandergerutscht..
Vielleicht hilft das weiter
[mm] n=\summe_{d/n}^{}\phi(d)
[/mm]
mit Mobiusinversion also
[mm] \phi(n)=\summe_{d/n}^{}\bruch{n}{d}\mu(d) [/mm] = [mm] n\summe_{d/n}^{}\bruch{\mu(d)}{d}
[/mm]
Vielleicht ist ja
[mm] \summe_{d/n}^{}\bruch{\mu(d)}{d} [/mm] > [mm] \bruch{1}{log(n)} [/mm] für genügend große n leichter zu zeigen??
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 23:49 Di 01.05.2007 | | Autor: | securido |
Verdammt, jetzt klappts schon nicht mal mehr mit dem grösser/kleiner Zeichen... 
Gemeint war selbstverstädlich:
$ [mm] \frac{\phi(n)}{n} [/mm] $ >$ [mm] \frac{\pi(n)}{n} [/mm] $ ~ $ [mm] \frac{1}{\ln n} [/mm] $ = $ [mm] \frac{\log e}{\log n} [/mm] $ > $ [mm] \frac{1}{\log n} [/mm] $
Wobei erste Ungleichung gilt nach der Ungleichung auf von wolfram.com deren Beweis mir schleierhaft ist, und die asymptotische Gleichheit nach dem Primzahlsatz.
Danke auch für den Tipp mit der Möbiusfunktion, sieht vielversprechen aus. Werde es mir morgen mal in Ruhe ansehen.
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 14:08 Do 17.05.2007 | | Autor: | Jack79 |
Hi,
hast du schon ein Ergebnis?
Ich brauche diese Abschätzung nämlich für eine Arbeit.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:20 Sa 19.05.2007 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
![[]](/images/popup.gif){kind=small}
http://math.uga.edu/~pete/4400arithmeticorders.pdf