Eigenschaft: endlich viele < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 10:22 Fr 18.05.2012 | | Autor: | sissile |
| Aufgabe | | Zeige: Zu jedem m [mm] \in \IN [/mm] gibt es nur endlich viele n [mm] \in \IN [/mm] mit der Eigenschaft [mm] \phi(n)=m [/mm] |
Ich glaube das müsste mit dem kleinen Fermat gehen.
$ [mm] \forall [/mm] $ a $ [mm] \in \IZ, [/mm] $ p teilt nicht a $ [mm] =>a^{p-1} \equiv [/mm] $ 1 (p)
Ich hatte auch viele kleinere Ansätz, haben aber alle nirgends wohin geführt.
Wie der hier zu nichts fürht:
Wähle Primzahl p
Angenommen p|n
m= [mm] \phi(n) [/mm] = n * [mm] \produkt_{p|n} [/mm] (1- 1/p)
-> p|m -> ggT(m,n)>1 da min. p groß
so p teilt nicht n
dh. nach Fermat [mm] n^{p-1} \equiv [/mm] 1 (p)
p| [mm] (n^{p-1} [/mm] -1)
Mit der endlichkeit der Anzahl der teiler, dachte ich, ist vlt. etwas zu machen. Aber dazu müsste n teiler von etwas sein.
lg
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 10:54 Fr 18.05.2012 | | Autor: | hippias |
Ich haette einen Tip: Versuche in
[mm] $\phi(n)= [/mm] n * [mm] \produkt_{p|n} [/mm] (1- 1/p)$ das Produkt [mm] $\produkt_{p|n} [/mm] (1- 1/p)$ nach unten abzuschaetzen und zwar nach Moeglichkeit durch [mm] $\phi(n)$. [/mm] Beachte dazu einerseits, dass $(1- [mm] 1/p)\geq \frac{1}{2}$ [/mm] ist, andererseits kann man [mm] $2^{k}$, [/mm] $k$ Anzahl der Primteiler von $n$, weiter durch [mm] $\phi(n)$ [/mm] abschaetzen. Naja, ist vielleicht doch eher eine Antwort statt Mitteilung geworden...
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 11:12 Fr 18.05.2012 | | Autor: | sissile |
Hallo,
danke für die antwort.
$ [mm] \phi(n)= [/mm] n [mm] \cdot{} \produkt_{p|n} [/mm] (1- 1/p) $<= n * [mm] (1/2)^k
[/mm]
k.. Anzahl der Primteiler von n
> $ [mm] 2^{k} [/mm] $, k Anzahl der Primteiler von n, weiter durch $ [mm] \phi(n) [/mm] $ abschaetzen.
Mit welchen Satz funktioniet die Abschätzung?
[mm] \phi(2^k) [/mm] = [mm] 2^k [/mm] - [mm] 2^{k-1} [/mm] = [mm] 2^{k-1} [/mm] *(2-1) = [mm] 2^{k-1}
[/mm]
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:45 Fr 18.05.2012 | | Autor: | hippias |
> Hallo,
> danke für die antwort.
>
> [mm]\phi(n)= n \cdot{} \produkt_{p|n} (1- 1/p) [/mm]<= n * [mm](1/2)^k[/mm]
> k.. Anzahl der Primteiler von n
>
> > [mm]2^{k} [/mm], k Anzahl der Primteiler von n, weiter durch [mm]\phi(n)[/mm]
> abschaetzen.
> Mit welchen Satz funktioniet die Abschätzung?
> [mm]\phi(2^k)[/mm] = [mm]2^k[/mm] - [mm]2^{k-1}[/mm] = [mm]2^{k-1}[/mm] *(2-1) = [mm]2^{k-1}[/mm]
Etwa so:Sei $n= [mm] \prod_{i=1}^{r} p_{i}^{e_{i}}$ [/mm] die Primfaktorzerlegung von $n$, d.h. [mm] $e_{i}\geq [/mm] 1$. Dann ist [mm] $\phi(n)= \prod_{i=1}^{r} (p_{i}-1)p_{i}^{e_{i}-1}$. [/mm] In jedem der Faktoren steckt eine $2$, ausser im Fall [mm] $p_{i}= [/mm] 2$ und [mm] $e_{i}= [/mm] 1$. Damit kann man etwas ueber [mm] $\phi(n)$ [/mm] und [mm] $2^{k}$ [/mm] aussagen.
|
|
|
|
