Eulersche Phi-Funktion

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 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\N \, |\, 1 \le a \le n \and \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 $\Bbb{Z}/n\Bbb{Z}$ zu.

Denn ist $\overline{a}\in\Bbb{Z}/n\Bbb{Z}$ eine Einheit, also $\overline{a}\in(\Bbb{Z}/n\Bbb{Z})^*,$ so gibt es ein $\overline{b}\in\Bbb{Z}/n\Bbb{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 riemannschen 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-\frac1{p}\right).$

Beispiel:

$\varphi(16)=\varphi(2^4)=2^4-2^3=2^3\cdot (2-1)=2^4\cdot \left(1-\frac12\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