- Euler’sche φ-Funktion
-
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.
Inhaltsverzeichnis
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 zehn Werte der -Funktion lauten:
-
n 1 2 3 4 5 6 7 8 9 10 teilerfremde
Reste1 1 1, 2 1, 3 1, 2, 3, 4 1, 5 1, 2, 3, 4, 5, 6 1, 3, 5, 7 1, 2, 4, 5, 7, 8 1, 3, 7, 9 1 1 2 2 4 2 6 4 6 4
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
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 an 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 pk mit einer Primzahl p als Basis und einer natürlichen Zahl k als Exponent hat mit p nur einen Primfaktor. Infolgedessen hat pk nur mit Vielfachen von p einen von eins verschiedenen gemeinsamen Teiler. Im Bereich von 1 bis pk sind das die Zahlen
Das sind pk − 1 Zahlen, die nicht teilerfremd zu pk 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
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.
Weblinks
- Die ersten 10000 Werte der -Funktion
- Programme zur -Funktion
- Folge der Funktionswerte (n): Folge A000010 in OEIS
Wikimedia Foundation.