Eulersche Phi-Funktion/Chinesischer Restsatz/Berechnung/Bemerkung

Aus Wikiversity

Aus der Einheitenversion des Chinesischen Restsatzes folgt für die Eulersche Funktion, wenn die Primfaktorzerlegung ist, die Identität

Man muss also nur noch für eine Primzahl berechnen, wobei natürlich ist. Für mit ist eine Zahl genau dann teilerfremd zu , wenn sie teilerfremd zu ist, und das ist genau dann der Fall, wenn sie kein Vielfaches von ist. Die Vielfachen von im beschriebenen Intervall sind genau die Zahlen  mit . Dies sind Stück, so dass es also Einheiten gibt. Wir erhalten demnach

und insgesamt