Eulersche Phi-Funktion Beweis < Kombinatorik < Stochastik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 16:38 So 05.12.2010 | | Autor: | qsxqsx |
Hallo,
Die Eulersche Phi Funktion zu n gibt die Anzahl Zahlen an, welche keinen gemeinsamen Teiler ausser die 1 mit n haben.
Bsp: Falls n eine Primzahl ist, so ist [mm] \phi(n) [/mm] = n-1
Für eine Zahl n = [mm] p_{1}^{k_{1}}*...*p_{m}^{k_{m}} [/mm] , wobei [mm] p_{i} [/mm] jeweils verschiedene Primzahlen sind, steht dass gilt
[mm] \phi(n) [/mm] = [mm] \produkt_{i=1}^{m}(p_{i} [/mm] - [mm] 1)*p_{i}^{k_{i} - 1}
[/mm]
Ich will was einfacheres Zeigen, nämlich den Fall, wo alle Potenzen [mm] k_{i} [/mm] = 1 sind, woraus folgt
[mm] \phi(n) [/mm] = [mm] \produkt_{i=1}^{m}(p_{i} [/mm] - 1),
,mit n = [mm] p_{1}*p_{2}*...*p_{m}
[/mm]
Mein Versuch dies zu zeigen:
[mm] \produkt_{i=1}^{m}(p_{i} [/mm] - 1) = n - "Alle Möglichkeiten mit den m Primzahlen Zahlen zu bilden"
= [mm] p_{1}*p_{2}*...*p_{m} [/mm] - [mm] \summe_{a=1}^{m} \vektor{m \\ a}
[/mm]
= [mm] p_{1}*p_{2}*...*p_{m} [/mm] - [mm] (2^{m} [/mm] - 1)
Das Problem ist, dass das nicht stimmt. Sieht jemand meinen Denkfehler? Bräuchte nur einen Tipp.
Danke sehr!
Hier auf Wiki steht eigentlich schon der Beweis für sogar verschiedene Potenzen k von [mm] p_{i}. [/mm] Also n = [mm] p_{1}^{k_{1}}*...*p_{m}^{k_{m}} [/mm] Trotzdem möchte ich gerne sehen, dass es auch auf meine Art geht. ![[]](/images/popup.gif) Eulersche Phi Funktion
Gruss
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 17:08 So 05.12.2010 | | Autor: | qsxqsx |
Sry, ich habe gerade selber erst jetzt einen Fehler in meinem Prinzip erkannt. Wenn ich es doch nicht schaffe melde ich mich.
Gruss
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:23 So 12.12.2010 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
