- 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.