Die eulersche Phi-Funktion (andere Schreibweise: Eulersche φ-Funktion, auch eulersche Funktion genannt) ist eine zahlentheoretische Funktion. Sie gibt für jede positive natürliche Zahl an, wie viele zu teilerfremde positive natürliche Zahlen es gibt, die nicht größer als sind (auch als Totient von bezeichnet).
Ihr Funktionswert ist gleich der Anzahl der zu teilerfremden Reste modulo . Für liegt er im Bereich .
Der Name Phi-Funktion geht auf Leonhard Euler zurück.
Definition
Die Phi-Funktion ist definiert durch und
Dabei bezeichnet den größten gemeinsamen Teiler von und
Eine andere, trivialerweise äquivalente, Schreibweise ist die Darstellung als Summe:
Beispiele
- Die Zahl 1 enthält als Leeres Produkt keinen Primfaktor und ist zu allen Zahlen, auch zu sich selbst, teilerfremd, also ist
- 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 jedem die Anzahl der Einheiten im Restklassenring zu, also die Ordnung 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 dem Exponenten 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 jedes aus dessen kanonischer Primfaktorzerlegung
berechnen, indem man die Multiplikativität und die Formel für Primzahlpotenzen anwendet:
- ,
wobei die Produkte über alle Primzahlen , die Teiler von sind, gebildet werden.
Beispiel:
oder
- .
Durchschnittliche Größenordnung
Mit der riemannschen Zetafunktion , dem Landau-Symbol und gilt:
Wegen sind diese beiden Summen asymptotisch gleich:
Man sagt dazu auch:
- Die durchschnittliche Größenordnung von ist
Fourier-Transformation
Die eulersche Phifunktion ist die diskrete Fourier-Transformation des ggT, ausgewertet an der Stelle 1:
Nimmt man auf beiden Seiten den Realteil, ergibt sich die Gleichung
Weitere Beziehungen
- Es gilt für ungerade sogar
- Für gilt:
- Für alle 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 und teilerfremd sind, ist ein Teiler von
Etwas anders formuliert:
Ein Spezialfall (für Primzahlen ) 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.
Die Phi-Funktion kommt auch in dem Kriterium für die Konstruierbarkeit eines Polygons vor.
Siehe auch
Weblinks
- Eric W. Weisstein: Totient Function. In: MathWorld (englisch).
- Folge der Funktionswerte Folge A000010 in OEIS
- Die ersten 100.000 Werte der Phi-Funktion (OEIS)
- Phi-Rechner (englisch)
- Florian Luca, Herman te Riele: and : from Euler to Erdös. Nieuw Archief voor Wiskunde, März 2011 (PDF; 304 kB).
- Video: Die Eulersche Phi-Funktion. Pädagogische Hochschule Heidelberg (PHHD) 2012, zur Verfügung gestellt von der Technischen Informationsbibliothek (TIB), doi:10.5446/19894.
Einzelnachweise
- ↑ Wolfgang Schramm: The Fourier transform of functions of the greatest common divisor. In: Integers Electronic Journal of Combinatorial Number Theory. 8. Jahrgang. University of West Georgia, Karls-Universität Prag, 2008, S. A50 (colgate.edu [abgerufen am 31. Mai 2021]).
- ↑ Johannes Buchmann: Einführung in die Kryptographie. Theorem 3.8.4.