3. Elementare Zahlentheorie

D Kongruenzrechnung in Z

Eulersche φ-Funktion: Berechnungsformel

Der Wert der eulerschen Phi-Funktion lässt sich für jede natürliche Zahl n aus deren kanonischer Primfaktorzerlegung
 
n = ∏p∣n pkp
 
berechnen:
 
φ(n) = ∏p∣n pkp−1(p−1) = n ∏p∣n (1−(1/ p))
 
wobei die Produkte über alle Primzahlen p, die Teiler von n sind, gebildet werden. Diese Formel folgt direkt aus der Multiplikativität der Phi-Funktion und der Formel für Primzahlpotenzen.

Diskussion