Die ersten tausend Werte der Funktion
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.
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:

- 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
|
00+
|
|
01 |
01 |
02 |
02 |
04 |
02 |
06 |
04 |
06
|
10+
|
04 |
10 |
04 |
12 |
06 |
08 |
08 |
16 |
06 |
18
|
20+
|
08 |
12 |
10 |
22 |
08 |
20 |
12 |
18 |
12 |
28
|
30+
|
08 |
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
|
Die Phi-Funktion ist eine multiplikative zahlentheoretische Funktion, sodass für teilerfremde Zahlen
und

gilt. Ein Beispiel dazu:

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.
Die Dirichlet-erzeugende Funktion der Phi-Funktion hängt mit der riemannschen Zetafunktion
zusammen:

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

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:
.
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
.
Mit der riemannschen Zetafunktion
, dem Landau-Symbol
und
gilt:

Wegen
sind diese beiden Summen asymptotisch gleich:

Man sagt dazu auch:
Die eulersche Phifunktion ist die diskrete Fourier-Transformation des ggT, ausgewertet an der Stelle 1:[1]
![{\displaystyle {\begin{aligned}{\mathcal {F}}\left\{\mathbf {x} \right\}[m]&=\sum \limits _{k=1}^{n}x_{k}\cdot e^{-2\pi i{\frac {mk}{n}}},\quad \mathbf {x_{k}} =\left\{\operatorname {ggT} (k,n)\right\}\quad {\text{für }}\,k\in \left\{1,\dotsc ,n\right\}\\\varphi (n)&={\mathcal {F}}\left\{\mathbf {x} \right\}[1]=\sum \limits _{k=1}^{n}\operatorname {ggT} (k,n)e^{-2\pi i{\frac {k}{n}}}\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/95052f791b719faf16447f07084aaa2819ed5591)
Nimmt man auf beiden Seiten den Realteil, ergibt sich die Gleichung

- Es gilt
für ungerade
sogar 
- Für
gilt:

- Für alle
gilt:[2]

- Beispiel: Für
ist die Menge
der positiven Teiler von
durch

- gegeben. Addition der zugehörigen
Gleichungen

- ergibt:

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