Direkt zum Inhalt

Lexikon der Mathematik: Eulersche φ-Funktion

Eulersche Funktion, zahlentheoretische Funktion, die wie folgt definiert werden kann.

Zu einer natürlichen Zahl m bezeichnet man mit φ(m) die Anzahl der zu m teilerfremden natürlichen Zahlen, die kleiner als m sind.

Es ist z.B. φ(6) = 2, da 1 und 5 die einzigen natürlichen Zahlen < 6 sind, die zugleich zu 6 teilerfremd sind, und φ(10) = 4.

Für eine Primzahl p ist φ(p) = p − 1, da eine Primzahl außer der 1 keine echten Teiler besitzt.

Für jedes m ist φ(m) die Ordnung der primen Restklassengruppe modulo m.

Euler führte 1760 die φ-Funktion ein; sie spielt eine Rolle bei seiner Verallgemeinerung des kleinen Satzes von Fermat zum Satz von Fermat-Euler.

Die Eulersche φ-Funktion ist eine multiplikative Funktion, d. h., es gilt φ(mn) = φ(m)φ(n), wenn m und n teilerfremd sind, und besitzt die geschlossene Darstellung \begin{eqnarray}\phi (m)=m\displaystyle \prod _{p|m}\left(1-\frac{1}{p}\right),\end{eqnarray} wobei sich das Produkt über alle Primteiler von m erstreckt. Eine andere wichtige Formel ist \begin{eqnarray}m=\displaystyle \sum _{d|m}\phi (d),\end{eqnarray} wobei über alle Teiler von m summiert wird, sowie die Beziehung φ(n2) = nφ(n), die sich aus der oben genannten Multiplikativität ergibt.

Interessant ist die Frage nach der Werteverteilung der φ-Funktion. Man bezeichne mit Vφ(n) die Eulersche Vielfachheit von n, d. h., Vφ(n) ist die Anzahl derjenigen natürlichen Zahlen m, die die Gleichung φ(m) = n erfüllen. Die Carmichaelsche Vermutung besagt, daß Vφ(n) ≠ 1 für alle n ∈ ℕ; Sierpinski vermutete, daß es zu jedem k ≥ 2 eine Zahl n ∈ ℕ mit Vφ(n) = k gibt. Beide Vermutungen sind noch offen.

Ein anderes Problem zur Werteverteilung ist die Frage nach der Asymptotik der Anzahlfunktion der Wertemenge von φ: Es bezeichne W(x) die Anzahl der Zahlen nx mit Vφ(n) ≥ 1; Ford konnte 1998 die Divergenzordnung von W(x) für x → ∞ durch eine komplizierte Funktion bestimmen.

  • Die Autoren
- Prof. Dr. Guido Walz

Schreiben Sie uns!

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

Partnerinhalte

Bitte erlauben Sie Javascript, um die volle Funktionalität von Spektrum.de zu erhalten.