Arithmetische Funktion φ(n), die die positiven ganzen Zahlen ≤ n zählt, die zu n teilerfremd sind; äquivalent die Ordnung der multiplikativen Einheitengruppe modulo n.

Prinzip

Multiplikativ und auf Primpotenzen gegeben durch φ(p^a) = p^a − p^{a−1}; allgemein φ(n) = n ∏_{p|n} (1 − 1/p) für n ≥ 1. Sie drückt aus, wie Primteiler die Zahl invertierbarer Reste vermindern.

Demonstration

Beispiel: n = 12 hat die Primfaktorzerlegung 2^2·3, also φ(12) = 12·(1−1/2)·(1−1/3) = 12·1/2·2/3 = 4; die invertierbaren Reste modulo 12 sind {1,5,7,11}.

Fehlanwendung

φ für nichtganzzahlige Eingaben verwenden, Multiplikativität ohne Koprimalitätsbedingung anwenden (z. B. φ(ab)=φ(a)φ(b) auch wenn gcd(a,b)≠1), oder φ(n) mit der Anzahl der Primfaktoren verwechseln führt zu falschen Schlüssen.

Konsequenz

φ(n) bestimmt die Struktur und Größe von (Z/nZ)^×, bildet die Grundlage von Eulers Satz a^{φ(n)} ≡ 1 (mod n) für gcd(a,n)=1 und ist zentral in der Public-Key-Kryptographie sowie in gruppentheoretischen Zählargumenten der Zahlentheorie.

Umkehrung

Die komplementäre Sicht ist, die nicht teilerfremden Reste zu zählen (n − φ(n)) oder die Exponentenfunktion (Carmichael-Funktion λ(n)) zu betrachten, die das kleinste e mit a^e ≡ 1 (mod n) für alle Einheiten misst, statt der Gruppenordnung.

Abgrenzung

Definiert für positive ganze Zahlen n (mit φ(1)=1); Erweiterungen auf rationale oder reelle Argumente behalten nicht dieselben arithmetischen Eigenschaften. Multiplikativität gilt nur über paarweise teilerfremde Faktoren; Formeln basieren auf der Primfaktorzerlegung.

Semantische Spannung

Wird oft der Carmichael-Funktion λ(n) gegenübergestellt (betrifft Exponenten nicht Ordnung) und Funktionen, die Primfaktoren zählen; Verwechslungen entstehen, wenn Ordnung mit Exponent gleichgesetzt oder lokales Verhalten mit globalen Mittelwerten verwechselt wird.

Synthese

Eulers Totientfunktion φ(n) ist das multiplikative arithmetische Maß dafür, wie viele Residuen modulo n invertierbar sind; aus der Primpotenzzerlegung berechenbar, verbindet sie lokale Primhindernisse mit globaler Gruppenordnung und dient vielfach in theoretischer und angewandter Zahlentheorie.