Hilft mir jemand beim Beweis der eulerschen Phi-Funktion für Primzahlen?
Ich schreibe gerade das Kapitel über die eulersche Phi-Funktion in meiner Seminararbeit und möchte folgendes beweisen:
Dafür habe ich mir folgenden Beweis abgekuckt und etwas umgeschrieben:
Meine Frage ist jetzt, wieso sind genau die q-1 Vielfachen von p und die p-1 Vielfachen von q nicht teilerfremd zu p*q. Also warum genau bis zu diesen Zahlen? Das Mathebuch, aus dem ich diesen Beweis habe, hat das einfach als trivial angenommen und nicht weiter ausgeführt, aber ich bin dafür leider etwas zu blöd xD. Danke schonmal für eure Hilfe!
2 Antworten
Du willst ja die Anzahl der natürlichen Zahlen bestimmen die kleiner als p*q sind und nicht teilerfremd zu p*q sind.
Da wie gesagt p und q prim sind, ist eine solche Zahl genau dann nicht teilerfremd zu p*q wenn die Zahl durch p oder q teilbar ist.
Es gibt genau (p-1) natürliche Zahlen die kleiner als p*q und durch q teilbar sind. (q, 2q, 3q... (p-1)a) und genauso gibt es (q-1) Zahlen die kleiner als q und durch p teilbar sind. Beide Mengen sind disjunkt, da die kleinste natürliche Zahl, die sowohl durch p als auch q teilbar ist, p*q ist. (Und alle anderen vielfachen von p bzw wo sind offensichtlich größer oder gleich p*q)
Die Antwort ist wirklich trivial.
Überleg doch mal:
Wenn n eine Primzahl ist, welchen Wert hat dann phi(n)?