Multiplikative Funktionen < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
Es handelt sich um die eulersche Phi-Funktion.
Definiert ist:
p und q seien Primzahlen mit p [mm] \not= [/mm] q
n = (p*q)
Wir sollen herausfinden wieso Φ(n) = Φ(p) * Φ(q)
Ich habe mir gedacht, dass ich die Anzahl der nicht relativ primen, positiven, ganzen Zahlen von der Anzahl der positiven, ganzen Zahlen, die < n sind, subtrahieren werden müssten.
So entspreche es ja dann auch der Definition von eulerschen Phi-Funktionen. Also:
Φ(n) = (pq - 1) - [(p - 1) + (q - 1)]
Da ich weiß, dass für die eulersche Phi-Funktion Φ(p) = p - 1 gilt für alle Primzahlen p, müsste am Ende der Umformung also
Φ (n) = (p - 1) * (q - 1)
herauskommen.
Jetzt weiß ich aber nicht wie ich weiter machen soll. Ich schaffe es irgendwie nicht das ganze Umzuformen.
Das waren meine Überlegungen:
Φ(n) = (pq - 1) - [(p - 1) + (q - 1)]
Φ(n) = (pq - 1) - (p-1) - (q-1)
Φ(n) = pq + (-1) + (-p) + 1 + (-q) + 1
Φ(n) = pq + 1 - (p + q)
Φ(n) = ???
Jetzt weiß ich einfach nicht weiter. Habe ich etwas falsch umgeformt?
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 10:46 Sa 23.02.2013 | | Autor: | M.Rex |
Hallo
> Es handelt sich um die eulersche Phi-Funktion.
>
> Definiert ist:
> p und q seien Primzahlen mit p [mm]\not=[/mm] q
> n = (p*q)
>
> Wir sollen herausfinden wieso Φ(n) = Φ(p) * Φ(q)
>
> Ich habe mir gedacht, dass ich die Anzahl der nicht relativ
> primen, positiven, ganzen Zahlen von der Anzahl der
> positiven, ganzen Zahlen, die < n sind, subtrahieren werden
> müssten.
>
> So entspreche es ja dann auch der Definition von eulerschen
> Phi-Funktionen. Also:
>
> Φ(n) = (pq - 1) - [(p - 1) + (q - 1)]
>
> Da ich weiß, dass für die eulersche Phi-Funktion Φ(p) =
> p - 1 gilt für alle Primzahlen p, müsste am Ende der
> Umformung also
> Φ (n) = (p - 1) * (q - 1)
> herauskommen.
>
> Jetzt weiß ich aber nicht wie ich weiter machen soll. Ich
> schaffe es irgendwie nicht das ganze Umzuformen.
>
> Das waren meine Überlegungen:
>
> Φ(n) = (pq - 1) - [(p - 1) + (q - 1)]
> Φ(n) = (pq - 1) - (p-1) - (q-1)
> Φ(n) = pq + (-1) + (-p) + 1 + (-q) + 1
> Φ(n) = pq + 1 - (p + q)
> Φ(n) = ???
>
> Jetzt weiß ich einfach nicht weiter. Habe ich etwas falsch
> umgeformt?
Es gilt doch (p-1)(q-1)=pq-p-q+1, und genau das hsat du, wenn du die Minusklammer auflöst, da stehen.
Marius
|
|
|
|
