Die eulersche -Funktion (auch eulersche Funktion genannt) ist eine zahlentheoretische Funktion. Sie gibt für jede natürliche Zahl n an, wie viele positive ganze Zahlen zu ihr teilerfremd sind:

Dabei bezeichnet den größten gemeinsamen Teiler von a und n.

Die -Funktion ist benannt nach Leonhard Euler und wird mit dem griechischen Buchstaben (phi) bezeichnet.

Beispiele

• Die Zahl 6 ist zu zwei der Zahlen von 1 bis 6 teilerfremd (1 und 5), also ist .
• Die Zahl 13 ist als Primzahl zu den zwölf Zahlen 1 bis 12 teilerfremd, also ist (13) = 12.

Die ersten 99 Werte der -Funktion lauten:

Eigenschaften

Multiplikative Funktion

Die -Funktion ist eine multiplikative zahlentheoretische Funktion. Das heißt, dass für teilerfremde Zahlen m und n die Gleichung

gilt. Beispielsweise ist

.

Dichte

Die Funktion gibt die Anzahl der Einheiten im Restklassenring an.

Denn ist eine Einheit, also , so gibt es ein mit .

Was äquivalent zu und ist, wenn man geeignet wählt.

Nach dem Lemma von Bézout ist dies äquivalent zur Teilerfremdheit von und .

ist für n > 2 stets eine gerade Zahl.

Ist a_n die Anzahl der Elemente aus dem Bild , die kleinergleich n sind, dann gilt .

Das Bild der -Funktion besitzt also natürliche Dichte 0.

Berechnung

Primzahlen

Da jede Primzahl p nur durch 1 und sich selbst teilbar ist, ist sie zu den Zahlen 1 bis p − 1 teilerfremd. Es gilt daher

Potenz von Primzahlen

Eine Potenz p^k mit einer Primzahl p als Basis und einer natürlichen Zahl k als Exponent hat mit p nur einen Primfaktor. Infolgedessen hat p^k nur mit Vielfachen von p einen von eins verschiedenen gemeinsamen Teiler. Im Bereich von 1 bis p^k sind das die Zahlen

Das sind p^{k − 1} Zahlen, die nicht teilerfremd zu p^k sind. Für die eulersche -Funktion gilt deshalb die Formel

Beispiel:

Allgemeine Berechnungsformel

Der Wert der eulerschen -Funktion lässt sich für jede Zahl aus ihrer kanonischen Primfaktorzerlegung

berechnen:

Diese Formel folgt direkt aus der Multiplikativität der -Funktion und der Formel für Primzahlpotenzen.

Beispiel:

Abschätzung

Eine Abschätzung für das arithmetische Mittel von (n) erhält man über die Formel

,

wobei ζ die riemannsche Zetafunktion und O das Landau-Symbol ist.

Das heißt: Im Mittel ist

Weitere Beziehungen

Für gilt:

Bedeutung der -Funktion

Eine der wichtigsten Anwendungen findet die -Funktion im Satz von Fermat-Euler:

Wenn zwei ganze Zahlen a und m ≥ 2 teilerfremd sind, gilt:

(m teilt a hoch Phi von m minus 1),

oder anders formuliert:

Ein Spezialfall (für Primzahlen p) dieses Satzes ist der kleine fermatsche Satz:

,

bzw.

Der Satz von Fermat-Euler findet unter anderem Anwendung bei der Generierung von Schlüsseln für das RSA-Verfahren in der Kryptographie.

Die ersten 100000 Werte der -Funktion

Programme zur -Funktion

Folge der Funktionswerte (n): Folge A000010 in OEIS

Kategorie: Zahlentheoretische Funktion