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 $n$ an, wie viele zu $n$ teilerfremde positive ganze Zahlen es gibt, die nicht größer als $n$ sind:

\varphi (n)\;:=\;{\Big |}\{a\in \mathbb {N} \,|\,1\leq a\leq n\land \operatorname {ggT} (a,n)=1\}{\Big |}

Dabei bezeichnet $\operatorname {ggT} (a,n)$ den größten gemeinsamen Teiler von $a$ und $n.$

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 $\!\ \varphi (6)=2.$
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 $\!\ \varphi (13)=12.$

Die ersten 99 Werte der Phi-Funktion lauten:

$\varphi (n)$	+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 $m$ und $n$

\varphi (m\cdot n)=\varphi (m)\cdot \varphi (n)

gilt. Ein Beispiel dazu:

\varphi (18)=\varphi (2)\cdot \varphi (9)=1\cdot 6=6

Dichte

Die Funktion $\varphi \,$ ordnet jeder natürlichen Zahl $n$ die Anzahl $\varphi (n)\,$ der Einheiten im Restklassenring ${\mathbb {Z}}/n{\mathbb {Z}}$ zu.

Denn ist ${\overline {a}}\in {\mathbb {Z}}/n{\mathbb {Z}}$ eine Einheit, also ${\overline {a}}\in ({\mathbb {Z}}/n{\mathbb {Z}})^{*},$ so gibt es ein ${\overline {b}}\in {\mathbb {Z}}/n{\mathbb {Z}}$ mit ${\overline {a}}\cdot {\overline {b}}={\overline {1}},$ was äquivalent zu $ab\equiv 1\,\mathrm {mod} \,n,$ also zur Existenz einer ganzen Zahl $x$ mit $ab+nx=1\,$ ist.

Nach dem Lemma von Bézout ist dies äquivalent zur Teilerfremdheit von $a\,$ und $n.$

$\varphi (n)$ ist für $n>2$ stets eine gerade Zahl.

Ist $a_{n}$ die Anzahl der Elemente im Bild $\mathrm {im} (\varphi ),$ die nicht größer als $n$ sind, dann gilt $\lim _{n\to \infty }{\frac {a_{n}}{n}}=0.$

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 riemannsche Zetafunktion $\zeta$ zusammen:

\sum _{n=1}^{\infty }{\frac {\varphi (n)}{n^{s}}}={\frac {\zeta (s-1)}{\zeta (s)}}

Berechnung

Primzahlen

Da eine Primzahl $p$ nur durch 1 und sich selbst teilbar ist, ist sie zu den Zahlen 1 bis $p-1$ teilerfremd. Weil sie größer als 1 ist, ist sie außerdem nicht zu sich selbst teilerfremd. Es gilt daher

\varphi (p)=p-1.

Potenz von Primzahlen

Eine Potenz $p^{k}$ mit einer Primzahl $p$ als Basis und einer positiven ganzen Zahl $k$ als Exponent hat nur den einen Primfaktor $p.$ Daher hat $p^{k}$ nur mit Vielfachen von $p$ einen von 1 verschiedenen gemeinsamen Teiler. Im Bereich von 1 bis $p^{k}$ sind das die Zahlen

1\cdot p,2\cdot p,3\cdot p,\cdots ,p^{k-1}\cdot p=p^{k}.

Das sind $p^{k-1}$ Zahlen, die nicht teilerfremd zu $p^{k}$ sind. Für die eulersche $\!\ \varphi$ -Funktion gilt deshalb

\varphi (p^{k})=p^{k}-p^{k-1}=p^{k-1}(p-1)=p^{k}\left(1-{\frac {1}{p}}\right).

Beispiel:

\varphi (16)=\varphi (2^{4})=2^{4}-2^{3}=2^{3}\cdot (2-1)=2^{4}\cdot \left(1-{\frac {1}{2}}\right)=8

Allgemeine Berechnungsformel

Der Wert der eulerschen Phi-Funktion lässt sich für jede Zahl aus ihrer kanonischen Primfaktorzerlegung

n=\prod _{p\mid n}p^{k_{p}}

berechnen:

\varphi (n)=\prod _{p\mid n}p^{k_{p}-1}(p-1)=n\prod _{p\mid n}\left(1-{\frac {1}{p}}\right)

Diese Formel folgt direkt aus der Multiplikativität der Phi-Funktion und der Formel für Primzahlpotenzen.

Beispiel:

\varphi (72)=\varphi (2^{3}\cdot 3^{2})=2^{3-1}\cdot (2-1)\cdot 3^{2-1}\cdot (3-1)=2^{2}\cdot 1\cdot 3\cdot 2=24

Abschätzung

Eine Abschätzung für das arithmetische Mittel von $\!\ \varphi (n)$ erhält man über die Formel

\sum _{n=1}^{N}\varphi (n)={\frac {1}{2\zeta (2)}}N^{2}+{\mathcal {O}}(N\log N),

wobei ζ die riemannsche Zetafunktion und ${\mathcal {O}}$ das Landau-Symbol ist.

Das heißt: Im Mittel ist $\varphi (n)\approx n{\frac {3}{\pi ^{2}}}.$

Weitere Beziehungen

Für $n\geq 2$ gilt:

\sum _{1\leq j\leq n-1 \atop (n,j)=1}j={\frac {n}{2}}\varphi (n)

Bedeutung

Eine wichtige Anwendung findet die Phi-Funktion im Satz von Fermat-Euler:

Wenn zwei positive ganze Zahlen a und m teilerfremd sind, ist m ein Teiler von $a^{\varphi (m)}-1:$

\operatorname {ggT} (a,m)=1\Rightarrow m\mid a^{\varphi (m)}-1

Etwas anders formuliert:

\operatorname {ggT} (a,m)=1\Rightarrow a^{\varphi (m)}\equiv 1{\pmod {m}}

Ein Spezialfall (für Primzahlen p) dieses Satzes ist der kleine fermatsche Satz:

p\nmid a\Rightarrow p\mid a^{p-1}-1

p\nmid a\Rightarrow a^{p-1}\equiv 1{\pmod {p}}

Der Satz von Fermat-Euler findet unter anderem Anwendung beim Erzeugen von Schlüsseln für das RSA-Verfahren in der Kryptographie.

Weblinks

Die ersten 100000 Werte der Phi-Funktion
Programme zur $\varphi$ -Funktion
Folge der Funktionswerte $\varphi (n):$ Folge A000010 in OEIS

Deutschland 1933 und 1945

Eulersche Phi-Funktion

Inhaltsverzeichnis

Beispiele