4. Die Eulersche φ-Funktion

Die Eulersche φ-Funktion gibt für jede positive Zahl m an, wie viele zu m teilerfremde Zahlen im Intervall zwischen 1 und m liegen. Diese zahlentheoretische Funktion spielt eine Schlüsselrolle in der Theorie der Kongruenzen. Sie ist ein Paradebeispiel für eine multiplikative Funktion, also eine Funktion f : ℕ* → ℕ* mit der Eigenschaft

f (m₁ m₂)  =  f (m₁) f (m₂)  für alle teilerfremden m₁, m₂ ≥ 1.