Eulersche Phi-Funktion
Die eulersche Phi-Funktion (andere Schreibweise: Eulersche φ-Funktion, auch eulersche Funktion genannt) ist eine zahlentheoretische Funktion. Sie gibt für jede natürliche Zahl an, wie viele zu teilerfremde natürliche Zahlen es gibt, die nicht größer als sind:
Dabei bezeichnet den größten gemeinsamen Teiler von und Außerdem wird hier und im ganzen weiteren Artikel unter der Menge der natürlichen Zahlen die Menge der positiven ganzen Zahlen verstanden, sodass also stets gilt.
Die Phi-Funktion ist benannt nach Leonhard Euler.
Beispiele
- Die Zahl 6 ist zu genau zwei der sechs Zahlen von 1 bis 6 teilerfremd (nämlich zu 1 und zu 5), also ist
- Die Zahl 13 ist als Primzahl zu jeder der zwölf Zahlen von 1 bis 12 teilerfremd (aber natürlich nicht zu 13), also ist
Die ersten 99 Werte der Phi-Funktion lauten:
+0 | +1 | +2 | +3 | +4 | +5 | +6 | +7 | +8 | +9 | |
---|---|---|---|---|---|---|---|---|---|---|
0+ | 1 | 1 | 2 | 2 | 4 | 2 | 6 | 4 | 6 | |
10+ | 4 | 10 | 4 | 12 | 6 | 8 | 8 | 16 | 6 | 18 |
20+ | 8 | 12 | 10 | 22 | 8 | 20 | 12 | 18 | 12 | 28 |
30+ | 8 | 30 | 16 | 20 | 16 | 24 | 12 | 36 | 18 | 24 |
40+ | 16 | 40 | 12 | 42 | 20 | 24 | 22 | 46 | 16 | 42 |
50+ | 20 | 32 | 24 | 52 | 18 | 40 | 24 | 36 | 28 | 58 |
60+ | 16 | 60 | 30 | 36 | 32 | 48 | 20 | 66 | 32 | 44 |
70+ | 24 | 70 | 24 | 72 | 36 | 40 | 36 | 60 | 24 | 78 |
80+ | 32 | 54 | 40 | 82 | 24 | 64 | 42 | 56 | 40 | 88 |
90+ | 24 | 72 | 44 | 60 | 46 | 72 | 32 | 96 | 42 | 60 |
Eigenschaften
Multiplikative Funktion
Die Phi-Funktion ist eine multiplikative zahlentheoretische Funktion, sodass für teilerfremde Zahlen und
gilt. Ein Beispiel dazu:
Eigenschaften
Die Funktion ordnet jeder natürlichen Zahl die Anzahl der Einheiten im Restklassenring zu, also dieOrdnung der primen Restklassengruppe.
Denn ist eine Einheit, also so gibt es ein mit was äquivalent zu also zur Existenz einer ganzen Zahl mit ist. Nach dem Lemma von Bézout ist dies äquivalent zur Teilerfremdheit von und
ist für stets eine gerade Zahl.
Ist die Anzahl der Elemente im Bild die nicht größer als sind, dann gilt
Das Bild der Phi-Funktion besitzt also die natürliche Dichte 0.
Erzeugende Funktion
Die Dirichlet-erzeugende Funktion der Phi-Funktion hängt mit der riemannschen Zetafunktion zusammen:
Berechnung
Primzahlen
Da eine Primzahl nur durch 1 und sich selbst teilbar ist, ist sie zu den Zahlen 1 bis teilerfremd. Weil sie größer als 1 ist, ist sie außerdem nicht zu sich selbst teilerfremd. Es gilt daher
Potenz von Primzahlen
Eine Potenz mit einer Primzahl als Basis und einer natürlichen Zahl als Exponent hat nur den einen Primfaktor Daher hat nur mit Vielfachen von einen von 1 verschiedenen gemeinsamen Teiler. Im Bereich von 1 bis sind das die Zahlen
Das sind Zahlen, die nicht teilerfremd zu sind. Für die eulersche -Funktion gilt deshalb
Beispiel:
Allgemeine Berechnungsformel
Der Wert der eulerschen Phi-Funktion lässt sich für jede natürliche Zahl aus deren kanonischer Primfaktorzerlegung
berechnen:
- ,
wobei die Produkte über alle Primzahlen , die Teiler von sind, gebildet werden. Diese Formel folgt direkt aus der Multiplikativität der Phi-Funktion und der Formel für Primzahlpotenzen.
Beispiel:
oder
- .
Abschätzung
Eine Abschätzung für das arithmetische Mittel von erhält man über die Formel
wobei ζ die riemannsche Zetafunktion und das Landau-Symbol ist.
Das heißt: Im Mittel ist .
Fourier-Transformation
Die eulersche Phifunktion ist die diskrete Fourier-Transformation des ggT, ausgewertet an der Stelle 1:
Der Realteil davon ergibt die Gleichung
Weitere Beziehungen
- Für gilt:
- Für alle natürlichen Zahlen gilt:
- Beispiel: Für
ist die Menge
der positiven Teiler von
durch
- gegeben. Addition der zugehörigen
Gleichungen
- ergibt:
Bedeutung
Eine wichtige Anwendung findet die Phi-Funktion im Satz von Fermat-Euler:
Wenn zwei natürliche Zahlen a und m teilerfremd sind, ist m ein Teiler von
Etwas anders formuliert:
Ein Spezialfall (für Primzahlen p) dieses Satzes ist der kleine fermatsche Satz:
Der Satz von Fermat-Euler findet unter anderem Anwendung beim Erzeugen von Schlüsseln für das RSA-Verfahren in der Kryptographie.
Basierend auf einem Artikel in: Wikipedia.deSeite zurück
© biancahoegel.de
Datum der letzten Änderung: Jena, den: 31.07. 2022