Euler´sche Phi Funktion < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Hallo Leute,
ich hab mal eine Frage.
Es geht um die Euler´sche Phi Funktion (ich benuzte hier mal [mm]\delta[/mm] statt phi)
Könnt Ihr mir sagen wie man auf diese Formel kommt? Quasi eine Herleitung.
Dies ist ja die Formel für Primzahlen mit Potenzen.
[mm] \delta (p^k) [/mm] = p^(k-1) * (p-1)
das is ja quasi das selbe wie [mm] p^k [/mm] - p^(k-1)
Ich komm einfach nicht darauf wie man das herleiten kann.
Ich hab fälschlicher weise dies vermutet.
Da PHI(p) = p-1 ist (p => Primzahl) gilt [mm] PHI(p^k)=p^k [/mm] - k*1
Das war auch nur ein dummer ansatz, aber in den Regeln steht das man wenigstens etwas eigenes vorweisen sollte, was auch sinnvoll ist ;)
Aber so wirklich viel kann ich ja, wie Ihr seht nicht vorweisen...
Ich hoffe es hilft mir trotzdem jmd ;)
Bei der Suche bin ich leider auf nix hilfreiches gestossen.
LG
TheEraser
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 13:26 Sa 04.08.2007 | | Autor: | Blech |
> Ich habe diese Frage in keinem Forum auf anderen
> Internetseiten gestellt.
>
> Hallo Leute,
>
> ich hab mal eine Frage.
>
> Es geht um die Euler´sche Phi Funktion (ich benuzte hier
> mal [mm]\delta[/mm] statt phi)
>
> Könnt Ihr mir sagen wie man auf diese Formel kommt? Quasi
> eine Herleitung.
> Dies ist ja die Formel für Primzahlen mit Potenzen.
>
> [mm]\delta (p^k)[/mm] = p^(k-1) * (p-1)
>
> das is ja quasi das selbe wie [mm]p^k[/mm] - p^(k-1)
>
> Ich komm einfach nicht darauf wie man das herleiten kann.
Kommt drauf an, was Du verwenden darfst.
Da p prim ist, ist [mm]p^k[/mm] wegen Primfaktorzerlegung zu allen Zahlen außer Vielfachen von p (die [mm] \leq p^k[/mm] sind) teilerfremd. Also zu allem außer [mm]\{1\cdot p, 2 \cdot p, \dots, p^{k-1} \cdot p\}[/mm]
[mm]\varphi(p^k)[/mm] ist dann einfach alles, was übrigbleibt.
[mm]\Rightarrow \varphi(p^k) = p^k - p^{k-1}[/mm]
> Bei der Suche bin ich leider auf nix hilfreiches
> gestossen.
Ich würde fast wetten, daß auf wikipedia was ähnliches wie oben steht.
|
|
|
| |
|
Hi, ich würds genausomachen wie Blech
[mm]\varphi(p^{k}) = \{ x \in \IZ_{p^{k}} : \gcd(x, p^{k}) = 1\} [/mm]
Da p ja nun Prim ist ist p auf jeden Fall teilerfremd zu allen Zahlen < p.
[mm]\IZ_{p^{k}} [/mm] hat genau [mm] p^{k} [/mm] Elemente.
Von diesen [mm] p^{k} [/mm] Elementen haben aber nur alle Vielfachen von p
einen ggT > 1 mit [mm] p^{k} [/mm] (1*p, 2*p, 3*p, ...., [mm](\frac{p^{k}}{p})*p[/mm]
Also insgesamt [mm]\frac{p^{k}}{p}[/mm] Elemente mit ggT > 1
=> [mm]\varphi(p^{k}) = p^{k} - \frac{p^{k}}{p} = p^{k} - p^{k-1}[/mm]
|
|
|
|
