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, sodass es also
Einheiten gibt. Wir erhalten demnach
-
und insgesamt
-