# Eulersche Phi-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 $n$ an, wie viele zu $n$ teilerfremde positive natürliche Zahlen es gibt, die nicht größer als $n$ sind (auch als Totient von $n$ bezeichnet).
Ihr Funktionswert $\varphi (n)$ ist gleich der Anzahl der zu $n$ teilerfremden Reste modulo $n$. Für $n>1$ liegt er im Bereich $1\leq \varphi (n)<n$.
Der Name Phi-Funktion geht auf Leonhard Euler zurück.
Die Phi-Funktion entscheidet über die Konstruierbarkeit eines Polygons in Abhängigkeit von der Anzahl der Ecken des Vielecks $n$. Genau dann, wenn der Phi-Funktionswert $\varphi (n)$ von der Anzahl der Ecken $n$ des betroffenen Polygons eine Zweierpotenz $\varphi (n)=2^{m}\quad {\text{mit}}\quad m\in \mathbb {N}$ ist, ist das $n$-Eck mit Zirkel und Lineal konstruierbar. Dies ist genau dann der Fall, wenn $n$ das Produkt einer Zweierpotenz und paarweise verschiedener Fermatscher Primzahlen ist.

## Definition

Die Phi-Funktion ist definiert durch $\varphi \colon \mathbb {N} ^{+}\to \mathbb {N} ^{+}$ und
    $\varphi (n)\;:=\;{\Big |}\{a\in \mathbb {N} \,\mid \,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.$
Eine andere, trivialerweise äquivalente, Schreibweise ist die Darstellung als Summe:
    $\varphi (n)\;=\;\sum \limits _{\overset {1\leq a\leq n}{\operatorname {ggT} (a,n)=1}}1$

## Beispiele

* Die Zahl 1 enthält als Leeres Produkt keinen Primfaktor und ist zu allen Zahlen, auch zu sich selbst, teilerfremd, also ist $\varphi (1)=1.$
* 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 |
| 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 |

## 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$
Ein geometrisch ausschlaggebendes weiteres Beispiel hierfür lautet:
    $\varphi (85)=\varphi (5)\cdot \varphi (17)=4\cdot 16=64$
Das bedeutet, dass das reguläre 85-Eck sehr wohl mit Zirkel und Lineal konstruiert werden kann.
Denn der Phi-Funktionswert von der 85, also die 64 ist eine Zweierpotenz.

### Eigenschaften

Die Funktion $\varphi$ ordnet jedem $n\in \mathbb {N} ^{+}$ die Anzahl $\varphi (n)$ der Einheiten im Restklassenring $\mathbb {Z} /n\mathbb {Z}$ zu, also die Ordnung 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{\bmod {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 dem Exponenten $k\in \mathbb {N} ^{+}$ 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,\;\dotsc ,\;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 jedes $n\in \mathbb {N} ^{+}$ aus dessen kanonischer Primfaktorzerlegung
    $n=\prod _{p\mid n}p^{k_{p}}$
berechnen, indem man die Multiplikativität und die Formel für Primzahlpotenzen anwendet:
    $\varphi (n)=\prod _{p\mid n}\varphi (p^{k_{p}})=\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 $p$, die Teiler von $n$ sind, gebildet werden.
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$.

### Durchschnittliche Größenordnung

Mit der riemannschen Zetafunktion $\zeta$, dem Landau-Symbol ${\mathcal {O}}$ und $\zeta (2)={\tfrac {\pi ^{2}}{6}}$ gilt:
    $\sum _{n=1}^{N}\varphi (n)={\frac {1}{2\zeta (2)}}N^{2}+{\mathcal {O}}(N\log N)={\frac {3}{\pi ^{2}}}N^{2}+{\mathcal {O}}(N\log N)$
Wegen $\sum _{n=1}^{N}{\tfrac {6}{\pi ^{2}}}n={\tfrac {6}{\pi ^{2}}}{\tfrac {N(N+1)}{2}}={\tfrac {3}{\pi ^{2}}}N^{2}+{\mathcal {O}}(N)$ sind diese beiden Summen asymptotisch gleich:
    $\lim _{N\to \infty }{\frac {\sum _{n=1}^{N}\varphi (n)}{\sum _{n=1}^{N}{\frac {6}{\pi ^{2}}}n}}=\lim _{N\to \infty }{\frac {{\frac {3}{\pi ^{2}}}+{\mathcal {O}}\left({\frac {\log N}{N}}\right)}{{\frac {3}{\pi ^{2}}}+{\mathcal {O}}\left({\frac {1}{N}}\right)}}=1$
Man sagt dazu auch:
* Die durchschnittliche Größenordnung von $\varphi (n)$ ist ${\tfrac {6}{\pi ^{2}}}n.$

### Fourier-Transformation

Die eulersche Phifunktion ist die diskrete Fourier-Transformation des ggT, ausgewertet an der Stelle 1:
    ${\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}}$
Nimmt man auf beiden Seiten den Realteil, ergibt sich die Gleichung
    $\varphi (n)=\sum \limits _{k=1}^{n}\operatorname {ggT} (k,n)\cos \left(2\pi {\frac {k}{n}}\right).$

### Weitere Beziehungen

* Es gilt $\varphi (n)>{\frac {\sqrt {n}}{2}},$ für ungerade $n$ sogar $\varphi (n)\geq {\sqrt {n}}.$
* Für $n\geq 2$ gilt:
       $\sum _{1\leq j\leq n-1 \atop \operatorname {ggT} (n,j)=1}j={\frac {n}{2}}\varphi (n)$
* Für alle $n\in \mathbb {N} ^{+}$ gilt:
       $\sum _{d>0 \atop d\mid n}\varphi (d)=n$
    Beispiel: Für $n=100$ ist die Menge $T(n):=\{t\in \ N^{+}\;{\big |}\;t\vert n\}$ der positiven Teiler von $n$ durch
       $T(100)=T(2^{2}\cdot 5^{2})=\left\{2^{m}\cdot 5^{n}\mid m\in \{0,1,2\},n\in \{0,1,2\}\right\}=\{1,2,4,5,10,20,25,50,100\}$
    gegeben. Addition der zugehörigen $|T(100)|=(2+1)(2+1)=9$ Gleichungen
       ${\begin{aligned}\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{aligned}}$
    ergibt:
       ${\begin{aligned}\sum _{d>0 \atop d\mid 100}\varphi (d)&=\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=100\end{aligned}}$

## 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\colon$
    $\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{\bmod {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{\bmod {p}}$
Der Satz von Fermat-Euler findet unter anderem Anwendung beim Erzeugen von Schlüsseln für das RSA-Verfahren in der Kryptographie.
Der $\varphi$-Funktionswert ist gemäß der bereits im Einleitungsteil des Artikels genannten Konstruierbarkeit eines Polygons das entscheidende Kriterium.