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 an, wie viele zu teilerfremde natürliche Zahlen es gibt, die nicht größer als 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 und Außerdem wird hier und im ganzen weiteren Artikel unter der Menge $\mathbb {N}$ der natürlichen Zahlen die Menge der positiven ganzen Zahlen verstanden, sodass also stets $0\notin \mathbb{N}$ 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 $\!\ \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 und

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

gilt. Ein Beispiel dazu:

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

Eigenschaften

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

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 mit $ab+nx=1\,$ ist. Nach dem Lemma von Bézout ist dies äquivalent zur Teilerfremdheit von $a\,$ und

$\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 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 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 als Basis und einer natürlichen Zahl als Exponent hat nur den einen Primfaktor Daher hat $p^{k}$ nur mit Vielfachen von 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 12}\right)=8$

Allgemeine Berechnungsformel

Der Wert der eulerschen Phi-Funktion lässt sich für jede natürliche Zahl aus deren kanonischer 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)$ ,

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:

$\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$

oder

$\varphi(72) = 72 \cdot (1 - \tfrac{1}{2}) \cdot (1 - \tfrac{1}{3}) = 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}}}.$ .

Fourier-Transformation

Die eulersche Phifunktion ist die diskrete Fourier-Transformation des ggT, ausgewertet an der Stelle 1:

$\begin{align} \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 \dots 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{align}$

Der Realteil davon ergibt die Gleichung

$\varphi (n)=\sum\limits_{k=1}^n \operatorname{ggT}(k,n) \cos({2\pi\frac{k}{n})}.$

Weitere Beziehungen

Für $n\geq 2$ gilt:

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

Für alle natürlichen Zahlen gilt:

$\sum_{d > 0 \atop d | n} \varphi(d)= n$

Beispiel: Für n=100

ist die Menge $T(n):=\{t\in\N: t|n\}$ der positiven Teiler von durch

$T(100) = T(2^2\cdot 5^2) = \{2^m\cdot 5^n: m \in \{0,1,2\}, n \in \{0,1,2\}\} = \{1,2,4,5,10,20,25,50,100\}$

gegeben. Addition der zugehörigen |T(100)| = (2+1)(2+1) = 9

Gleichungen

$\begin{align} \varphi(1)&=1\\ \varphi(2)&=1\\ \varphi(4)&=2\\ \varphi(5)&=4\\ \varphi(10)&=4\\ \varphi(20)&=8\\ \varphi(25)&=20\\ \varphi(50)&=20\\ \varphi(100)&=40 \end{align}$

ergibt:

$\begin{align} \varphi(1)+\varphi(2)+\varphi(4)+\varphi(5)+\varphi(10)+\varphi(20)+\varphi(25)+\varphi(50)+\varphi(100)&=1+1+2+4+4+8+20+20+40\\ \sum_{d > 0 \atop d | 100} \varphi(d)&=100 \end{align}$

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

Basierend auf einem Artikel in:

Wikipedia.de

$\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

$\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

$\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